First show that .
Assume is true for .
Then .
Now show that is equal to .
Your instructor may insist that 'strong induction' should be used.
Proofs, doncha love 'um? ... Well, I guess some of you might...
Anyway, down to business.
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 >.<