enter image description here

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!

  • $\begingroup$ 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}$... $\endgroup$ – Guest Mar 31 '14 at 0:36
  • 1
    $\begingroup$ Use mathematical induction. $\endgroup$ – Git Gud Mar 31 '14 at 0:36
  • 2
    $\begingroup$ 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? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.