# How to Use Math Induction to prove my formula?

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: ???

– Gary
Jan 17 at 2:20
• Square the 2^(2^(k-1)) and check that it is indeed 2^(2^([k+1]-1)). Jan 17 at 2:20

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$$?