Blogs, Mathematical Reasoning, MR Study Help

Induction Proof

In the following posts, we will be looking more at how to prove different theorems. In some of these, we will have to determine if the theorem is true, then prove that our answer is correct. You can find more examples of proof writing in the Study Help category for mathematical reasoning. You can also view the available videos on YouTube.

 

\(\sum\limits_{i=1}^{n}2^{i}=2^{n+1}-2\)

In this case, we are told that \(\sum\limits_{i=1}^{n}2^{i}=2^{n+1}-2\) for all \(n \in \mathbb{N}\), and we are asked to provide a proof. Because we believe this to be true, we don’t necessarily have to go through examples to determine why this is true. Instead, we can use induction here to verify that the equation holds for all \(n\). In order to use induction, we will first need to show the theorem is true for a base case, (here \(n=1\)), then assume it is true for \(n=k\) and show that this implies the theorem is true for \(k+1\). This then gives us that the theorem is always true.

Proof

Base Case

Let \(n=1\). Then \(\sum\limits_{i=1}^{1}2^{i}=2^{1}=2=4-2=2^{2}-2\). Hence, the equation holds for \(n=1\). In the proof, anything in parenthesis is meant to help you follow the process, but wouldn’t be included in a formal proof.

Induction Step

Assume that \(\sum\limits_{i=1}^{k}2^{i}=2^{k+1}-2\) (this is the induction hypothesis). We then have that
\begin{align*}
\sum_{i=1}^{k+1}2^{i}&=\sum_{i=1}^{k}2^{i}+2^{k+1}.
\end{align*}
(As part of induction with sums, we break up the sum from 1 to \(k+1\) as the sum from 1 to \(k\) and then add the \(k+1\) term. This will allow us to use the induction hypothesis to simplify the given expression).
\begin{align*}
\sum_{i=1}^{k+1}2^{i}&=\sum_{i=1}^{k}2^{i}+2^{k+1} \\
&=2^{k+1}-2+2^{k+1} \\
&=2(2^{k+1})-2 \\
&=2^{(k+1)+1}-2.
\end{align*}
(This precisely give us the equality we needed to show. Therefore, we know that if the theorem is true for the \(k\)th term, it must be true for the \(k+1\) term).

Hence, \(\sum\limits_{i=1}^{n}2^{i}=2^{n+1}-2\) for all \(n \in \mathbb{N}\).

Conclusion

In this situation we wanted to show that an equation was true for all natural numbers. As we did so, we noticed that an induction proof would be the best way to show that equation was true. While we don’t go through why the theorem holds, we are able to give precise proof that it is true.

For more help with proofs, make sure to continue working on the other problems we have posted solutions for in Study Help. If you find these helpful, make sure to let other people know about them so that they can get help as well.

We'd love to hear your thoughts!

This site uses Akismet to reduce spam. Learn how your comment data is processed.