# Recursively defined sequences

So, this question has been giving me a little bit of trouble. It's supposed to be just a few lines, and I know that I don't need to write out the base case, recursive step, and restriction. I understand the concept as well, but I'm not sure how to prove it correctly. Basically, I have written out about 6 steps with both equations (a_n = n^n-1 and a_k+1 = 5a_k). I don't know if this is technically the proper way to prove it though. Any help would be appreciated!

• Just use simple induction... the base step is clearly verified and then $a_{k+1} = 5 a_k = 5 \times 5^{k-1} = 5^{(k+1)-1}$... – Guest Mar 31 '14 at 0:36
• Use mathematical induction. – Git Gud Mar 31 '14 at 0:36
• It's a question whether there's even anything to prove. In most formal developments, a recurrence very close to this is what defines exponentiation in the first place. Do you have a particular definition of what $5^{n-1}$ means that you're supposed to show this from? – Henning Makholm Mar 31 '14 at 1:58

We will define $5^k$ as follows: $5^0$ will mean 1, and if $i$ is a positive integer, $5^i$ will mean $5\cdot5^{i-1}$.
Then we let $\Phi(k)$ be the statement $a_k = 5^{k-1}$. We want to show that $\Phi(k)$ holds for all $k\ge 1$, and we proceed by induction.
The base case is $\Phi(1)$, the statement that $a_1 = 5^0$. Since $a_1$ and $5^0$ are both defined to be 1, they are equal.
For the inductive step we suppose that $\Phi(k)$ is already known to be true and we want to prove that $\Phi(k+1)$ is true. That is, we suppose $$a_k = 5^{k-1}.$$ Multiplying both sides of this equation by 5, we obtain $$5a_k = 5\cdot5^{k-1}.$$ The left side is equal to $a_{k+1}$ by the definition we were given for the sequence, and the right side is equal to $5^k$ by the definition we adopted for $5^k$. So substituting equals for equals we have $$a_{k+1} = 5^k$$ which is precisely $\Phi(k+1)$, and we are done.