Recursion and Strong Induction

[andrew1]

Hi,

I'm currently having trouble with using strong induction to prove a recursive sequence and don't know where to begin, any help would be great thanks.

Define a recursive sequence f(0), f(1), f(2),... by
f(0) = 0
f(1) = 1
f(n+1) = 3f(n) + 10f(n-1), for all integers n>=1

Prove by strong induction that f(n) < 5^n for all integers n>=0

 

[kaliprasad]

Hi,

I'm currently having trouble with using strong induction to prove a recursive sequence and don't know where to begin, any help would be great thanks.

Define a recursive sequence f(0), f(1), f(2),... by
f(0) = 0
f(1) = 1
f(n+1) = 3f(n) + 10f(n-1), for all integers n>=1

Prove by strong induction that f(n) < 5^n for all integers n>=0

because f(1) < $5^1$ and f(0) = 0 <5 $^0$ base step is true

now we need to prove the induction step

$f(n ) < 5^n$
$f(n-1 ) < 5^{n-1}$
f(n+2) = 3 f(n) + 10 f(n-1)

< $3 * 5^n + 10 * 5^{n-1}$
< $3 * 5^n + 2 * 5^n$
< $5 * 5^n $
< $5^{n+1}$

so if it true for n and n-1 it is true for n+ 1
so induction step is proved
hence proved

 

[andrew1]

Thank you, but I'm confused as to how you arrived at that conclusion, could you provide a description of the process that you went through for each of the steps please.

 

[kaliprasad]

Thank you, but I'm confused as to how you arrived at that conclusion, could you provide a description of the process that you went through for each of the steps please.

can you explain in which step there was confusion.

 

[andrew1]

can you explain in which step there was confusion.

This part doesn't make much sense to me

< $3 * 5^n + 10 * 5^{n-1}$
< $3 * 5^n + 2 * 5^n$
< $5 * 5^n $
< $5^{n+1}$

 

[kaliprasad]

This part doesn't make much sense to me

< $3 * 5^n + 10 * 5^{n-1}$
< $3 * 5^n + 2 * 5^n$
< $5 * 5^n $
< $5^{n+1}$

OK \:
we have f(n) < $5^n$so 3 f( n) < 3 * 5^n

f(n-1) < $5^{n-1}$ it is true upto n so for all lower values

so f(n+1) = 3f(n) + 10 f(n-1)
< $3 * 5^n + 10 * 5^{n-1}$ (adding last 2)
< $3 * 5^n + 2 * 5 * 5^{n-1}$ (as 10 -= 2 * 5)
< $3 * 5^n + 2 * 5^n$
< $(3 + 2) * 5^n$
< $5 * 5^n$
< $5^{n+1}$

I hope now all steps are clear. I have just put the values and did arithmetic

 

[andrew1]

OK \:
we have f(n) < $5^n$so 3 f( n) < 3 * 5^n

f(n-1) < $5^{n-1}$ it is true upto n so for all lower values

so f(n+1) = 3f(n) + 10 f(n-1)
< $3 * 5^n + 10 * 5^{n-1}$ (adding last 2)
< $3 * 5^n + 2 * 5 * 5^{n-1}$ (as 10 -= 2 * 5)
< $3 * 5^n + 2 * 5^n$
< $(3 + 2) * 5^n$
< $5 * 5^n$
< $5^{n+1}$

I hope now all steps are clear. I have just put the values and did arithmetic

Hmmk, makes more sense now, strong induction always seems to confuse me :(