## rational 7 months ago help with induction proof http://prntscr.com/3hnvcf

1. rational

n = 1 : $$a_1 = 1 \lt 2^1$$ so the given statement is true for n = 1

2. Ilovecake

;)

3. Ilovecake

correct:)

4. rational

ty :) im clueless on next step :(

5. Ilovecake

oh

6. rational

would it be like induction proof from first principle : assume $$a_k = a_{k-1} + a_{k-2} + a_{k-3}\lt 2^k$$ and prove $$a_{k+1} \lt 2^k$$

7. myininaya

I would do three cases for the base case. For a1,a2,and a3. You want to assume your statement is true for every integer out to some chosen integer value k and then you want to show it is true for k+1. So let's consider the case of k+1 $a_{k+1}=a_k+a_{k-1}+a_{k-2}$ we need to look at a_(k-1) and a_k So we know a_k<2^k and a_(k-1)<2^(k-1) by our assumption

8. myininaya

oops and a_(k-2) so we have also a_(k-2)<2^(k-2)

9. rational

oh that makes sense 3 base cases ! and yes using second principle we have : $$a_{k} \lt 2^{k}$$ $$a_{k-1} \lt 2^{k-1}$$ $$a_{k-2} \lt 2^{k-2}$$

10. rational

$$a_{k+1}=a_k+a_{k-1}+a_{k-2} \lt 2^k + 2^{k-1} + 2^{k-2}$$

11. myininaya

yep good so far do you want to try to figure out the trick into showing <2^(k+1)?

12. rational

I'm trying at the moment lol, need to make the right hand side 2^{k+1}

13. myininaya

I used what I wanted to show to help me start out I don't know if that helps you

14. rational

im getting right hand side as : $$2^{k-2}(2^2 + 2 + 1) = 2^{k-2}(7)$$

15. rational

not sure how to conclude... only if that 7 was 8... :o

16. nipunmalhotra93

use 7<8

17. rational

it has to be $$\ge 8$$ i think

18. myininaya

I liked factoring out 2^(k+1) instead of 2^(k-2) but you should be able to proceed as you are

19. myininaya

and nip is right we want <

20. nipunmalhotra93

you have your term <2^(k-2) (7)<2^(k-2) (8)=2^(k+1)

21. rational

so far i have this : $$a_{k+1}=a_k+a_{k-1}+a_{k-2} \lt 2^k + 2^{k-1} + 2^{k-2} = 2^{k-2}(7)$$

22. rational

Ohhh yess !

23. nipunmalhotra93

yeah factoring out 2^(k+1) will do too.

24. rational

thanks a lot that was easier than it looked initally to start wid lol xD

25. myininaya

or I liked: $a_{k+1}<2^k+2^{k-1}+2^{k-2}=2^{k+1}(2^{-1}+2^{-2}+2^{-3})$ $=2^{k+1}(\frac{1}{2}+\frac{1}{4}+\frac{1}{8})=2^{k+1}(\frac{4+2+1}{8})=2^{k+1}\frac{7}{8}<2^{k+1} \frac{8}{8}=2^{k+1}(1)=2^{k+1}$ Both ways are cute

26. myininaya

both ways require you to know 7<8 that is interesting

27. nipunmalhotra93

yeah. :D

28. rational

hahah yes this looks easy to read quick :) thank you both :D

29. myininaya

hey rational here is another proof you can look at that has the same style we just worked with http://php.scripts.psu.edu/djh300/cmpsc360/ex-strong-induction.htm

30. nipunmalhotra93

you're welcome (Y)

31. rational

the proof in that link is very good !! cleared up the mechanics of strong induction thank you very much @myininaya