# Approach for solving recurrence relations using induction

This recurrence relation is for the famous problem The Tower of Hanoi.

We are given that: $$T_n=2T_{n-1}+1$$.

The problem here is, using induction, show that $$T_n=2^n – 1, n \ge 1$$
To make things simpler, I'll give the vague solution that has been given to us by our teachers.

##### Solution that I can't seem to understand:

Observe that $$T_1=1$$. If $$n\ge2,\,\,2T_{n-1}+1=2(2^{n-1}-1)+1=2^n-1=T_n$$, verifying the formula.

Given the solution, I tried applying the induction method on it, but I just can't seem to solve this problem. Could somebody please look at the solution above and help me understand the approach to solve such problems?

Similarly there are other problems that have been mentioned in our books, but I think if I get the approach for one, I'll be able to solve the others. Listing one of them here just so that it may give you'll any hints.

##### Power set problem:

Given $$S_n=2S_{n-1},n\ge1$$ with $$s_0=1$$, using the recurrence relation for $$S_n$$, show that $$Sn=2^n$$, $$n\ge0$$.

• Standard induction: (a) prove $T_1=f(1)$, (b) assuming $T_k=f(k)$ is true, prove $T_{k+1}=f(k+1)$, (c) claim $T_n=f(n)$ for all positive integer $n$ by induction Sep 29, 2022 at 16:25

When using mathematical induction to prove a certain property $$P(n)$$ we establish the basis of induction, e.g. that $$P(1)$$ is true and then prove that if $$P(n-1)$$ holds, the same happens to $$P(n)$$. In this case, what must be shown is that if $$T_{n-1} = 2^{n-1}-1$$ then $$T_{n} = 2^{n}-1$$. In fact, $$T_{n} = 2 \underbrace{T_{n-1}}_{=2^{n-1}-1}+1 = 2 \cdot (2^{n-1}-1)+1 = 2^n-2+1 = 2^n-1.$$

• $P(1)=2^1-1=1$, but how do I know this is true? I don't have a pattern on the L.H.S to compare with. Also, how did we establish that $T_{n-1}=2^{n-1}-1$? Sep 29, 2022 at 17:31
• Also, my problem is the 3rd step. I'm stuck at the 3rd step. $T_{k+1}=2^{k+1}-1$ and from here I'm lost. I don't know what needs to be proved from here on. Sep 29, 2022 at 17:45
• Also, in Mathematical induction, we we told to verify, $P(1)$, assume $P(k)$ is true and then verify $P(K+1)$ holds. Why have you taken $P(n-1)$ here? Sep 29, 2022 at 18:02

The solution given basically is induction, but with steps and some text skipped.

As user @Henry points out, the standard weak induction proofs (which is what you’ll be majorly/exclusively doing in intro to induction) go like this: For a statement $$P(n)$$ which is to be proven,

1. Prove that $$P(1)$$ holds, i.e. the statement is true when $$n=1$$ is plugged in. (Base Case)
2. Assume that $$P(k)$$ holds for some positive integer $$k$$, i.e. the statement is true when $$n=k$$ is plugged in. (Induction Hypothesis)
3. Based on (2), prove that $$P(k+1)$$ holds, i.e. the statement is true when $$n=k+1$$ is plugged in.

This works due to the theorem called the First Principle of Finite Induction, whose proof using the Well-Ordering Principle I link here. It basically states that:

Let S be a set of positive integers with the following properties:
(i) The integer $$1$$ belongs to S,
(ii) Whenever the integer $$k$$ is in S, the next integer $$k+1$$ must also be in S.
Then S is the set of all positive integers.

So a proof using induction would basically read like:
Let S be the set of all positive integers $$n$$ for which $$P(n): T_n =2^n-1$$ is true.
We know that $$1\in S$$, because $$T_1=2^1-1$$.
ASSUME that $$k\in S$$ for some positive integer $$k$$, i.e. $$T_k=2^k-1$$.
Then, by the given recurrence, $$T_{k+1}=2T_k+1$$ we have $$T_{k+1}=2^{k+1}-1$$.
This means that $$k+1\in S$$.
By the First Principle of Finite Induction, $$S$$ is the set of all positive integers. But since S is the set of all integers for which $$P(n)$$ is true, it must mean that $$P(n): T_n=2^n-1$$ must be true for all positive integers $$n$$. Hence proved.

We generally omit all references to the set S in proofs by induction, and just go : P(1), check. Assume P(k) is true. P(k+1), check. Hence proved.
I hope you can now write a proof using the three-step algorithm presented above.

• Can you answer my doubts, posted in the comments of the answer posted by @PierreCarre? Oct 4, 2022 at 15:56
• First comment: we ASSUMED that $T_{n-1}=2^{n-1}$. Second comment: after proving that, you don’t need to prove anything. Just write “and hence the proof is complete, by mathematical induction”. Third comment: both are equivalent. We just prove that if a positive integer belongs to the solution set, then the next positive integer belongs to the solution set too. Oct 6, 2022 at 7:38
• Okay, one final doubt, $T_{1}=2^1−1=1$ how do I tell if this is true or not? Usually, in case of other problems there is a pattern on the L.H.S which helps us to determine whether the answer achieved belongs to the sequence or not (ex. $1+2+3+....n=\frac{n(n+1)}{2}$). Oct 7, 2022 at 3:00
• $T_1=1$ is found by hit and trial. Oct 7, 2022 at 4:57
• No, Let me put it this way. I have 1 as the value. But how can I tell this is the correct value? What if I had gotten 2 after solving this equation? How would I know that this value is true? Oct 7, 2022 at 8:20

After asking quite a few peers and checking some other online books, I finally found the correct answer to this induction proof. The proof goes as follows:

Step 1. Induction Basis:
Let us check if $$P(1)$$ base case holds true by plugging the value $$n=1$$.

$$T_n=2^n-1\\ T_1=2^1-1=2-1=1$$

As this proof is for Towers of Hanoi, the number of steps involved in moving just a single disk is 1.
Therefore, $$P(1)$$ holds true.

Step 2. Induction Hypothesis:
Let us assume that $$P(k)$$ holds true for arbitrary $$k>=1$$.

$$T_k=2^k-1\tag{1}\label{eq_one}$$

Step 3. Induction Step:
We need to prove that $$P(k+1)$$ also holds true. Hence we need to show that the following equality holds true.

$$T_{k+1}=2^{k+1}-1$$

As we already know, for moving $$(n)^{th}$$ disk in TOH it takes $$\mathbf{2(T_{n-1})+1}$$ steps.
Applying this same logic to our case of $$(k+1)^{th}$$ disk we get $$T_{k+1}=2(T_k)+1$$.

Solving $$\mathbf{T_{k+1}=2(T_k)+1}$$
$$=2(2^k-1)+1 \stackrel{\eqref{eq_one}}*$$
$$=2.2^k-2+1$$
$$=2.2^k-1$$
$$=2^{k+1}-1$$

Hence proved via Mathematical induction.