Proof: Recursion Equality

• Feb 17th 2009, 09:05 AM
ARD
Proof: Recursion Equality
Proofs, doncha love 'um? (Headbang) ... Well, I guess some of you might...

Define the function Q(n), (n is a Positive Integer) by
Q(0)=2,
Q(1)=6,
Q(x)=6Q(x-1)-5Q(x-2)
Prove by Induction Q(n) = (5^n)+1

I admit, I can't do proofs well to begin with. I can usually blunder through induction; but I don't know how to write it when it uses recursion without doing an ever-expanding blob of variables and equations that all look the same. (Thinking)

Any assistance you could provide would be very appreciated. (Bow)

I should note that I do understand what is going on... it just gives me a headache to try and prove it >.<
• Feb 17th 2009, 09:35 AM
Plato
First show that $Q(2)=5^2+1$.
Assume $Q(K)$ is true for $K>2$.
Then $Q(K+1)=6Q(K)-5Q(K-1)=6\left[5^K + 1\right]-5\left[5^{K-1} + 1\right]$.
Now show that is equal to $5^{K+1} + 1$.

Your instructor may insist that 'strong induction' should be used.
• Feb 17th 2009, 10:09 AM
ARD
Eureka!

That's what I needed, the rest is just fancy numbers...

6(5^n+1)-5((5^(n-1))+1)=
6(5^n)+6-5(5^(n-1))-5
6(5^n)-(5^n)+1
5(5^n)+1
(5^n+1)+1

Thus 6((5^n)+1)-5((5^(n-1))+1)=(5^n+1)+1
Proving Q(n+1)

Thank you!