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

1. rational Group Title

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

2. Ilovecake Group Title

;)

3. Ilovecake Group Title

correct:)

4. rational Group Title

ty :) im clueless on next step :(

5. Ilovecake Group Title

oh

6. rational Group Title

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 Group Title

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 Group Title

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

9. rational Group Title

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 Group Title

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

11. myininaya Group Title

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

12. rational Group Title

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

13. myininaya Group Title

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

14. rational Group Title

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

15. rational Group Title

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

16. nipunmalhotra93 Group Title

use 7<8

17. rational Group Title

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

18. myininaya Group Title

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

19. myininaya Group Title

and nip is right we want <

20. nipunmalhotra93 Group Title

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

21. rational Group Title

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 Group Title

Ohhh yess !

23. nipunmalhotra93 Group Title

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

24. rational Group Title

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

25. myininaya Group Title

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 Group Title

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

27. nipunmalhotra93 Group Title

yeah. :D

28. rational Group Title

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

29. myininaya Group Title

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 Group Title

you're welcome (Y)

31. rational Group Title

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