Question

help with induction proof
http://prntscr.com/3hnvcf

Answer 1

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

Answer 2

;)

Answer 3

correct:)

Answer 4

ty :) im clueless on next step :(

Answer 5

oh

Answer 6

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\)

Answer 7

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

Answer 8

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

Answer 9

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} \)

Answer 10

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

Answer 11

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

Answer 12

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

Answer 13

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

Answer 14

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

Answer 15

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

Answer 16

use 7<8

Answer 17

it has to be \(\ge 8 \) i think

Answer 18

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

Answer 19

and nip is right we want <

Answer 20

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

Answer 21

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)\)

Answer 22

Ohhh yess !

Answer 23

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

Answer 24

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

Answer 25

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

Answer 26

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

Answer 27

yeah. :D

Answer 28

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

Answer 29

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

Answer 30

you're welcome (Y)

Answer 31

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