Question

2 functions
a, b : N --> N are defined
\(a_0 =2; a_1 =2; a_{n+2}=a_{n+1} + a_n\)
\(b_0=2, b_1=2, b_{n+2} = b_{n+1} * b_n\)
Prove by induction that \(b_n \geq a_n\)
Please, help

Answer 1

For n = 0, \(a_2 = a_1 + a_0 = 4\\a_3 = 6 \\a_4 = 10\\a_5= 16\\a_6 = 26\),
Hence the sequence is {2,2,6,10,16,26,.....}

Answer 2

\[b _{2}=4\]\[b _{3}=8\]\[b _{4}=32\]\[b _{5}=256\]

Answer 3

Don't we have to find explicit formula for \(a_n, b_n\)?

Answer 4

i don't use any

Answer 5

Ok, show me more, please

Answer 6

My attempt: For a_n
Characteristic equation: r^2 -r -1 =0, \(r =\dfrac{1\pm\sqrt5}{2}\),
Then the solution is \(a_n = A (\dfrac{1+\sqrt5}{2})^n + B(\dfrac{1-\sqrt5}{2})^n\)
If n = 0, \(a_0 = 2 \), hence A + B = 2
If n=1, \(a_1 = 2, hence ~~ A (\dfrac{1+\sqrt5}{2}) + B(\dfrac{1-\sqrt5}{2})=2\)
We can solve for A and B to get the explicit formula for \(a_n\)
Do the same to find \(b_n\)
From then, use induction to prove that \(b_n \geq a_n\)
Am I right so far?

Answer 7

solving the recurrence relations looks more complicated than necessary

Answer 8

First of all, notice that both the given sequences are increasing and each term is \(\ge 2\)

Answer 9

Base case : \(a_0 = 2\ge 2=b_0\)

Induction Hypothesis : assume \(b_k\ge a_k\)

Induction step :
\(
b_{k+1} = b_{k} * b_{k-1}\\~\\

\ge a_k*b_{k-1}\\~\\
\ge a_k*2\\~\\
= a_k + a_k\\~\\
\ge a_k + a_{k-1}\\~\\
=a_{k+1}
\)

Answer 10

that should do

Answer 11

WWWWWWWWWoah!! you make it easy!@!:(:)

Answer 12

maybe work two terms in the base case because the recurrence relation is two levels deep

Answer 13

Got you, thank you so much.

Answer 14

I like ganeshie's answer here.

Answer 15

I have a question on residue.
I need find the least residue of 1! +2! +...+10! modulo 2.

Answer 16

But I would add a corollary that shows \(a_{n+1}\ge a_n\)

Answer 17

or k in this instance

Answer 18

that would make it more complete...

Answer 19

Can I argue: 2! = 0 mod 2
other are same
and 1! =1 mod 2
then 1! +2!+.....+10! = 1 mod 2
Is it ok?

Answer 20

looks good to me

Answer 21

The problem is I don't find any theorem or corollary in book support my argument.

Answer 22

which argument ?

Answer 23

I would say your residue argument relies solely on the properties of even and odd numbers

Answer 24

yeah we have, \(2\mid n!\) for all \(n\ge 2\).
so \(n!\equiv 0 \pmod{2}\) for all \(n\ge 2\)

Answer 25

and definition of factorial, since they must all be even

Answer 26

\(1! \equiv 1(mod2)\\2!\equiv 0 (mod 2)\\--------------------\\1! +2! \equiv 1 (mod 2)\)

This property.

Answer 27

That's a property? I thought it was just computation

Answer 28

since 1+2=3 and 2 is congruent to 1mod2

Answer 29

3*

Answer 30

Since I have to find the least residue of that sum modulo 7,12, 25 and I don't want to expand the factorial. I need some theorem allow me to add the left hand side together and add the right hand side together but I don't have it on my book. :(

Answer 31

I have something like
\(x \equiv 2 (mod n)\\x+2\equiv 2+2 (mod n)\)

Answer 32

Ahh, instate like chinese remainder them?

Answer 33

that's the only thing I recall that allows addition/mult on the mod side

Answer 34

It means I can add the same number both sides of the equivalence,

Answer 35

shouldn't the least res always be 1?

Answer 36

strike that, I can't prove it

Answer 37

if \(a\equiv c \pmod{n}\) and \(b\equiv d \pmod{n}\), then :

\(a+b \equiv c+d \pmod{n}\)

Answer 38

you want to prove that ?

Answer 39

oH, I have it also. oh, yeah!!

Answer 40

I mean, we can prove it is always an odd value for the first one but for the 7,how do we know zero is necessarily not occurring. and for 25 as well

Answer 41

since we can essentially write it as 1+2(n+1) where n+1= 2!/2+3!/2+...+10!/2