Question

A sequence is recursively defined by
T(0)=1
T(1)=2
T(n)=2T(n-1)+T(n-2) for n>=2
Prove that T(n)<=(5/2)n
for n>=0

Answer 1

for n=3 T(n)=12
so it's wrong

Answer 2

n=3 would be 8

Answer 3

T(2)=2T(1)+T(0)
T(2)=2(2)+1
T(2)=5

T(3)=2T(2)+T(1)
T(3)=2(5)+2
T(3)=12
`12 sounds right`

\(\large\rm T(3) \cancel{\le}\dfrac{5}{2}\cdot(3)\)
Hmm this inequality doesn't appear to hold true :(

Answer 4

Or is it supposed to be \(\large\rm \left(\dfrac{5}{2}\right)^n\) ?

Answer 5

yeah its raised to n

Answer 6

sorry i didnt catch that

Answer 7

Proof by Induction would be nice.
Hmm I'm trying to remember how to do that when our function is defined recursively though >,<

Answer 8

yeah induction would be great but yeah the recursive is the problem

Answer 9

Let n=2 be your base case (since it relies on previous information).
So we've shown that T(2)=5.\[\large\rm \left(\frac{5}{2}\right)^2=\frac{25}{4}=6.25\]
And \(\large\rm 5\le6.25\) so we've proven our base case, ya?

Answer 10

yes

Answer 11

Induction Hypothesis:
Assume n=k is true.
Meaning \(\large\rm T(k)=2T(k-1)+T(k-2)\) is assumed to be true.

Answer 12

Induction Step:
For n=k+1,\[\large\rm T(k+1)=2T(k)+T(k-1)\]And then this is what we need to work with, ya?

Answer 13

I hope you understand what I did on the right side,
That first term had a (k+1)-1 while the other had a (k+1)-2

Answer 14

I simplified them.

Answer 15

ok i follow this but how do deal with it being its recursive

Answer 16

Your goal in these induction problems is to find a way to relate your equation in your `induction step` back to the equation that is assumed true in your `induction hypothesis`.

Answer 17

Look at your equation again, \[\large\rm T(k+1)=2\color{orangered}{T(k)}+T(k-1)\]Do you see anything from your `Induction Hypothesis` that might help here?

Answer 18

Our Induction Hypothesis gave us this: \(\large\rm \color{orangered}{T(k)=2T(k-1)+T(k-2)}\)
Maybe we can use that, hmm

Answer 19

so sub in and simplify?

Answer 20

\[\large\rm T(k+1)=2\color{orangered}{(2T(k-1)+T(k-2))}+T(k-1)\]
Yah let's true that :)
Maybe it will lead us to something.

Answer 21

T(k+1)=2(2T(k−1)+T(k−2))+T(k−1)

Answer 22

man you type equations fast

Answer 23

Oh oh I missed sort of an important step.
With recursion, we can't simply assume that n=k is true.
We have to also assume that everything leading up to k is true.

Answer 24

T(k+1)=5T(k−1)+2T(k−2)

Answer 25

Oh wow I'm being a little sloppy here.
Sorry sorry.
One sec.

Answer 26

Our Induction Hypothesis is this:\[\large\rm for\qquad T(k)=2T(k-1)+T(k-2)\]
\[\large\rm T(k)\le\left(\frac{5}{2}\right)^k\qquad\qquad is~true\]We don't want to forget about that inequality! :O

Answer 27

oh ok yeah i guess that might be important =)

Answer 28

So then for,\[\large\rm T(k+1)=2\color{orangered}{T(k)}+T(k-1)\]\[\large\rm T(k+1)=2\color{orangered}{(2T(k-1)+T(k-2))}+T(k-1)\]\[\large\rm T(k+1)=5T(k-1)+2T(k-2)\]We want to prove:\[\large\rm T(k+1)\le\left(\frac{5}{2}\right)^{k+1}\]

Answer 29

5T(k−1)+2T(k−2)<= (5/2)^(k+1)

Answer 30

so should i try to simplify or just sub in a value for k?

Answer 31

Hmm that's not the way I was going to do it,
but I think this will work better actually...

Remember our induction step:
We assumed T(k) <= (5/2)^k.
But since our function is recursive, we have to assume every value up to k satisfies this relationship as well.

So T(k-1) <= (5/2)^(k-1) is true
and T(k-2) <= (5/2)^(k-2) is also true.

So ummm

Answer 32

So what I would say is this:\[\large\rm 5\color{green}{T(k-1)}+2\color{royalblue}{T(k-2)}\le 5\color{green}{\left(\frac{5}{2}\right)^{k-1}}+2\color{royalblue}{\left(\frac{5}{2}\right)^{k-2}}\]I can go into more detail if that's way too confusing :d

Answer 33

Hmm ya this is gonna get messy :[
Grr sorry, thinking..

Answer 34

np thank you

Answer 35

is there a way to pull out (5/2)^k−1 on the right side

Answer 36

We're trying to relate this to T(k+1).
So maybe we actually want to pull a (5/2)^(k+1) out of each term.

Answer 37

I feel like this is not the way they intended us to do the problem...
feels long and tedious, but it should work.

Answer 38

i agree. would the way you were thinking about before be better?

Answer 39

Factoring (5/2)^(k+1) out of each term,\[\large\rm 5\left(\frac{5}{2}\right)^{k-1}+2\left(\frac{5}{2}\right)^{k-2}=\left(\frac{5}{2}\right)^{k+1}\left[5\left(\frac{5}{2}\right)^{-2}+2\left(\frac{5}{2}\right)^{-3}\right]\]This mess in the brackets simplifies to a fraction, and is less than 1,\[\large\rm =\left(\frac{5}{2}\right)^{k+1}\left[\frac{116}{125}\right]\le \left(\frac{5}{2}\right)^{k+1}(1)\]Therefore,\[\large\rm T(k+1)\le \left(\frac{5}{2}\right)^{k+1}\]Hmm yah that wasn't the best way to do that :(
I'll keep thinking about it a little more.

Answer 40

agreed this is a messy way to do this but it did work. thank you so much!

Answer 41

5T(k−1)+2T(k−2)≤5(5/2)^(k−1)+2(5/2)^(k−2)

Answer 42

how did you get the right half?

Answer 43

T(0)=1
T(1)=2
T(n)=2T(n-1)+T(n-2) for n>=2
Prove that T(n)<=(5/2)^n
for n>=0

show base case:

Now assume the following:
\[T(k)=2T(k-1)+T(k-2) \le (\frac{5}{2})^k \text{ is true for some integer } k \ge 2 \\ \text{ now we want to show the following } \\ T(k+1)=2T(k)+T(k-1) \le (\frac{5}{2})^{k+1} ...\]

So let me start with the left hand side of the inequality (the inequality we want to show)
\[T(k+1)=2T(k)+T(k-1) \\ =2 [\color{red}{2 T(k-1)+T(k-2)}]+T(k-1) \text{ by induction hyp } \\ =4T(k-1)+2 T(k-2)-T(k-1) \\ =5 T(k-1)+2 T(k-2)\]
so cool stuff ...
now yeah I think I remember this being called "strong induction" that means we assume previous things to k to show the k+1 thingy...
To cool that @zepdrix used the following:
\[T(k-1) \le (\frac{5}{2})^{k-1} \text{ and } T(k-2 )\le (\frac{5}{2})^{k-2} \\ \\ \text{ so going back to our } T(k+1) \text{ thingy }\]

\[T(k+1)=5 T(k-1)+2T(k-2) \le 5 (\frac{5}{2})^{k-1}+2(\frac{5}{2})^{k-2} \\ \text{ now remember what we want to show that this is } \le (\frac{5}{2})^{k+1} \\ \text{ this is why he chose to factor out } (\frac{5}{2})^{k+1}\]

before we move on you show recall k-1 equals k+1-2
and k-2 is equal to k+1-3

So before we move on let me rewrite those exponents so it is a little more obvious what happen with those exponents

\[T(k+1)=5 T(k-1)+2 T(k-2) \\ T(k+1) \le 5 (\frac{5}{2})^{k+1-2}+2(\frac{5}{2})^{k+1-3} \\ T(k+1) \le 5(\frac{5}{2})^{k+1}(\frac{5}{2})^{-2}+2(\frac{5}{2})^{k+1}(\frac{5}{2})^{-3} \text{ by law of exponents } \\ T(k+1) \le (\frac{5}{2})^{k+1}(5 (\frac{5}{2})^{-2}+2(\frac{5}{2})^{-3}) \text{ by factoring }\]
any questions on the exponent part or factoring part?

Answer 44

awesome that makes sense now

Answer 45

By our assumption: \(\large\rm \color{orangered}{T(k-1)\le \left(\dfrac{5}{2}\right)^{k-1}}\)

Multiply by 5: \(\large\rm 5\color{orangered}{T(k-1)\le \color{black}{5}\left(\dfrac{5}{2}\right)^{k-1}}\)

Similarly, our assumption gave us: \(\large\rm \color{orangered}{T(k-2)\le \left(\dfrac{5}{2}\right)^{k-2}}\)

Multiplying by 2: \(\large\rm 2\color{orangered}{T(k-2)\le \color{black}{2}\left(\dfrac{5}{2}\right)^{k-2}}\)

And then adding those together. :o

Answer 46

does this sum it up correctly