Here's the question you clicked on:
n = 1 : \(a_1 = 1 \lt 2^1 \) so the given statement is true for n = 1
ty :) im clueless on next step :(
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\)
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
oops and a_(k-2) so we have also a_(k-2)<2^(k-2)
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} \)
\(a_{k+1}=a_k+a_{k-1}+a_{k-2} \lt 2^k + 2^{k-1} + 2^{k-2}\)
yep good so far do you want to try to figure out the trick into showing <2^(k+1)?
I'm trying at the moment lol, need to make the right hand side 2^{k+1}
I used what I wanted to show to help me start out I don't know if that helps you
im getting right hand side as : \(2^{k-2}(2^2 + 2 + 1) = 2^{k-2}(7)\)
not sure how to conclude... only if that 7 was 8... :o
it has to be \(\ge 8 \) i think
I liked factoring out 2^(k+1) instead of 2^(k-2) but you should be able to proceed as you are
and nip is right we want <
you have your term <2^(k-2) (7)<2^(k-2) (8)=2^(k+1)
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)\)
yeah factoring out 2^(k+1) will do too.
thanks a lot that was easier than it looked initally to start wid lol xD
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
both ways require you to know 7<8 that is interesting
hahah yes this looks easy to read quick :) thank you both :D
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
you're welcome (Y)
the proof in that link is very good !! cleared up the mechanics of strong induction thank you very much @myininaya