3
$\begingroup$

On day one, I was fined 2 dollars. Every subsequent day the fine is squared (i.e., day 1: 2, day 2: 4, day 3: 16, day 4: 256, day 5: 65,536). After some analysis, I came up with the formula to determine the fine amount D given the day N: D = $2^{2^{(N-1)}}$.

I am now trying to prove this formula is true using mathematical induction, but I do not know what to show for the k + 1 step. Assume N=k is true: D = $2^{2^{(k-1)}}$

Show k + 1 is true: ???

$\endgroup$
2
  • $\begingroup$ Please use MathJax to format your equations. $\endgroup$
    – Gary
    Jan 17 at 2:20
  • 1
    $\begingroup$ Square the 2^(2^(k-1)) and check that it is indeed 2^(2^([k+1]-1)). $\endgroup$ Jan 17 at 2:20

1 Answer 1

4
$\begingroup$

To figure out what to do, it helps to clarify two things:

  1. The fine amount $D$ is, first of all, a function of $N$. We can make this easier to keep in mind by writing it as $D_N$ or $D(N)$.
  2. We can phrase the information you're given as $D_1 = 2$ (on day $1$, you are fined $2$ dollars) and $D_N = (D_{N-1})^2$ (every day, the fine is squared).

Now, in the induction hypothesis, rather than saying "$N=k$ is true" which is vague and poorly phrased, we can be more precise. We are assuming that the formula we are trying to prove, that $D_N = 2^{2^{N-1}}$, holds when $N=k$. In other words, $D_k = 2^{2^{k-1}}$.

We are now trying to prove that this formula also holds for $N=k+1$: that $D_{k+1} = 2^{2^{k}}$. Can you prove this using the information you're given - that $D_{k+1} = (D_k)^2$?

$\endgroup$

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.