1. ## Proof: Recursion Equality

Proofs, doncha love 'um? ... 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.

Any assistance you could provide would be very appreciated.

I should note that I do understand what is going on... it just gives me a headache to try and prove it >.<

2. First show that $\displaystyle Q(2)=5^2+1$.
Assume $\displaystyle Q(K)$ is true for $\displaystyle K>2$.
Then $\displaystyle 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 $\displaystyle 5^{K+1} + 1$.

Your instructor may insist that 'strong induction' should be used.

3. 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!