rational
  • rational
help with induction proof http://prntscr.com/3hnvcf
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
schrodinger
  • schrodinger
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
rational
  • rational
n = 1 : \(a_1 = 1 \lt 2^1 \) so the given statement is true for n = 1
Ilovecake
  • Ilovecake
;)
Ilovecake
  • Ilovecake
correct:)

Looking for something else?

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

More answers

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