Can someone clarify step-by-step how to solve such Recursion & Induction question?

Question

I've a discrete math exam coming up in two weeks and the only thing I've problem with is induction and recursion. I do know how to check the base case of a certain induction i.e. check and compare if left side and right side are equal, but induction assumption step is awfully complex. Could someone explain every step of a such problem? $$\large{\sum_{i=1}^n 2^{i-1}=2^n-1}$$

Thanks in advance!

Answer 1

The base case: Show that the statement holds for $n = 1$.

We need to check that $\sum_{i=1}^1 2^{i-1} = 2^{1-1} = 1$ equals to $2^1 - 1 = 1$ which is true.

Inductive step: Show that if the statement holds for $n$, then it also holds for $n+1$.

So assume that the statement holds for $n$, that is $\sum_{i=1}^n 2^{i-1} = 2^{n} - 1$. Consider the left-hand side of the statement for $n+1$: $$\sum_{i=1}^{n+1} 2^{i-1} = 2^{(n+1)-1} + \sum_{i=1}^n 2^{i-1} = \{\text{using the statement for $n$}\} = 2^n + (2^n - 1)=$$ $$= 2\cdot 2^n - 1 = 2^{n+1}-1.$$

There is really nothing complicated going on, you just need to reduce the statement for $n+1$ to the statement for $n$ plus some extra stuff. In particalar, here we are extracting one of the summands to reduce the number of summands in the sum in order to use the assumption for $n$, which is a common trick in that kind of problems.

Hope this helps. If something is not clear, feel free to ask any questions.

Answer 2

Induction is used to prove that a property is true for all members of a set defined inductively. Examples of such sets could be (1) the set of natural numbers, (2) trees or (3) regular languages. Let me illustrate this point for the statement to be proved in the OP.

We want to prove that $\sum_{i=1}^n 2^{i-1} = 2^n - 1$ for all $i \ge 1$. The set of all natural numbers can be defined inductively as - (a) $1$ is a natural number and (b) if $n$ is a natural number then so is $n + 1$. (One start from $0$ as well, but sometimes the set $\{0, 1, 2, \ldots\}$ is called the set of whole numbers.)

Therefore, the base case in the proof, is $n = 1$. It is easy to prove that the equation is valid for the base case. Once we do so, we assume that the statement is true for $n = k$ and prove that it is true for $n = k + 1$, using only the cases $n \le k$. So, let's assume that $\sum_{i=1}^k 2^{i-1} = 2^k - 1$. We call is the 'induction hypothesis'.

Now, $\sum_{i=1}^{k+1} 2^{i-1} = \sum_{i=1}^k 2^{i-1} + 2^k$. The first term on the right follows from inductive hypothesis. Therefore, $\sum_{i=1}^{k+1} 2^{i-1} = 2^k - 1 + 2^k = 2\times 2^k - 1 = 2^{k+1} - 1$.

Since the validity for the case $n = k + 1$ follows from its predecessors, the statement is true for all natural numbers.

Answer 3

The inductive step consists in proving that for any $n$, once a formula has been established for $n$, the next case follows. Combined with the initial case, say $n=0$, the rationale is that you can prove the case $n$ in $n$ steps: since $n$ is established, case $1$ follows. Since case $2$ is true, case $3$ follows, &c.

Considering your particular formula, you can rewrite it as $$\sum_{i=0}^{n-1}2^i=2^n-1$$

Inductive step:

Suppose this formula is true for some, unspecified, $n$ (inductive hypothesis). For the next $n$, we have to consider $\;\displaystyle\sum_{i=0}^{n}2^i$, and prove that it is none other than $\;2^{n+1}-1$. Now \begin{align*} \sum_{i=0}^{n}2^i&=\sum_{i=0}^{n-1}2^i+2^n\\ &= (2^n-1)+2^n&&\text{by the inductive hypothesis}\\&=2\cdot 2^n-1=2^{n+1}-1. \end{align*}

Thus we have proved case $n$ implies case $n+1$, i. e. we have proved the inductive step.

Answer 4

Let's assume that you wish to prove some property $P(n)$ of the positive integers (or non-negative integers).

Induction proofs are based on two properties of the positive integers (or non-negative integers).

1. Each integer $n$ has a successor $n + 1$, meaning that there are no integers between $n$ and $n + 1$.
2. Any non-empty set of positive integers (or non-negative integers) has a least element.

In an induction proof of a property $P(n)$ of the positive integers (or non-negative integers), we first establish that the base case $P(n_0)$ holds. This establishes that the set of positive integers for which the statement holds is non-empty. Since $P(n_0)$ holds, we may assume there exists some integer $m$ such that $P(m)$ holds. We then establish that whenever $P(m)$ holds, then $P(m + 1)$ holds. Since $P(n_0)$ holds and $P(m + 1)$ holds whenever $P(m)$ holds, we then obtain the series of implications $$P(n_0) \Rightarrow P(n_0 + 1) \Rightarrow P(n_0 + 2) \Rightarrow P(n_0 + 3) \Rightarrow \cdots$$ which establishes that $P(n)$ holds for each positive integer $n \geq n_0$.

In your example, $n_0 = 1$.

Proof: (by mathematical induction on $n$) Let $P(n)$ be the statement $$\sum_{i = 1}^{n} 2^{i - 1} = 2^n - 1$$

Base step: We show $P(1)$ holds.

If $n = 1$, then $$\sum_{i = 1}^{1} 2^{i - 1} = 2^{1 - 1} = 2^0 = 1 = 2 - 1 = 2^1 - 1$$ so $P(1)$ holds.

Induction hypothesis: Since $P(1)$ holds, we may assume there exists a positive integer $m$ such that $P(m)$ holds. Thus, we have the induction hypothesis $$\color{blue}{\sum_{i = 1}^{m} 2^{i - 1} = 2^m - 1}$$

Inductive step: We show that $P(m) \Rightarrow P(m + 1)$. Let $n = m + 1$. Then \begin{align*} \sum_{i = 1}^{m + 1} 2^{i - 1} & = \sum_{i = 1}^m 2^{i - 1} + 2^{(m + 1) - 1}\\ & = \color{blue}{\sum_{i = 1}^m 2^{i - 1}} + 2^m\\ & = \color{blue}{2^m - 1} + 2^m && \text{by the induction hypothesis}\\ & = 2 \cdot 2^m - 1\\ & = 2^{m + 1} - 1 \end{align*} Thus, $P(m) \Rightarrow P(m + 1)$.

Since $P(1)$ holds and $P(m) \Rightarrow P(m + 1)$ whenever $P(m)$ holds, $P(n)$ holds for all positive integers.$\blacksquare$