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

- rational

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

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- schrodinger

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- rational

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

- Ilovecake

;)

- Ilovecake

correct:)

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- rational

ty :) im clueless on next step :(

- Ilovecake

oh

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

- 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

- myininaya

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

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

- rational

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

- myininaya

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

- rational

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

- myininaya

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

- rational

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

- rational

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

- nipunmalhotra93

use 7<8

- rational

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

- myininaya

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

- myininaya

and nip is right we want <

- nipunmalhotra93

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

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

- rational

Ohhh yess !

- nipunmalhotra93

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

- rational

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

- 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

- myininaya

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

- nipunmalhotra93

yeah. :D

- rational

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

- 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

- nipunmalhotra93

you're welcome (Y)

- rational

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

Looking for something else?

Not the answer you are looking for? Search for more explanations.