Lesson 2

It is not difficult to guess that \(T_{n}=2^{n}-1\). This can then be proven by induction.

• Base case \(n=1\).  \(T_{1}=1=2^{1}-1\).


• Step \(n \to n+1\).  \[\begin{align*}T_{n+1}&=2T_{n}+1&\text{(definition of \(T_{n+1}\))}\\&=2 \cdot (2^{n}-1)+1&\text{(induction hypothesis)}\\&=2^{n+1}-1.\end{align*}\]

Now, let's try to prove a weaker statement “\(T_{n} \le 2^{n}\)”. It is indeed weaker: whereas the statement “\(T_{n}=2^{n}-1\)” says that \(T_{n}\) is smaller than \(2^{n}\) by one, the statement “\(T_{n} \le 2^{n}\)” just says that it is at most \(2^{n}\) (and doesn't specify by how much). It is natural to expect that proving this weaker statement should only be easier. Surprisingly, the proof doesn't go through!

• Base case \(n=1\).  \(T_{1}=1 \le 2=2^{1}\).


• Step \(n \to n+1\).  \[\begin{align*}T_{n+1}&=2T_{n}+1&\text{(definition)}\\&\le 2 \cdot 2^{n}+1&\text{(induction hypothesis)}\\&=2^{n+1}+1 \\&\not \le 2^{n+1}\end{align*}\]

How is this possible?! Why is it possible to prove the stronger statement, but not the weaker one?