Question

I have u1 = u2 = 1
and u(n+2) = u(n+1) +u(n)
I need to prove that u(n) < 2^n using Maths Induction ( < means less than or equal to)
@ganeshie

Answer 1

So far I have the following.............

Answer 2

Assume P(k) is true u(k) < 2^k
and assume P(k+1) is also true u(k+1) < 2^k+1
Prove P(k+2)

P(k) + P(k+1) => u(k) + u(k+1) < 2^k + 2^k+1

Do you think this mathematically correct so far?

Answer 3

Shall I keep going along these lines because I do have a proof but I don't know if it's correct

Answer 4

Base case:
\(u(1) = 1 \lt 2^1\)
\(u(2) = 1 \lt 2^2\)

Induction hypothesis :
Let \(u(k)\lt 2^k\) and \(u(k-1)\lt 2^{k-1}\) for some arbitrary \(k\).

Induction step :
\(\begin{align}
u(k+1) &=u(k) + u(k-1)\\~\\
&\lt 2^k + 2^{k-1}\\~\\
&=2^{k-1}(2+1)\\~\\
&\lt 2^{k-1}(4)\\~\\
&=2^{k+1}
\end{align}\)
\(\blacksquare\)

Answer 5

Your steps are good :)

Answer 6

OK, that's great! That's what I needed. Thanks Ganeshie

Answer 7

Np, you could also use "strong induction" here

Answer 8

Can you explain that?

Answer 9

actually what we did is kind of strong induction only

Answer 10

we have assumed that the statement holds for u(k) and u(k-1)

Answer 11

in strong induction we assume that the statement holds form u(k), u(k-1), u(k-2), ....

then prove that the statement is true for u(k+1) too

Answer 12

http://math.stackexchange.com/questions/517440/whats-the-difference-between-simple-induction-and-strong-induction

Answer 13

OK, thanks for that extra bit of maths info.