Proof by induction that $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$

Question

I am trying to understand how to do proof by induction for inequalities. The step that I don't fully understand is making an assumption that n=k+1. For equations it is simple. For example:

Prove that 1+2+3+...+n = $ \frac {n(n+1)}{2} $ is valid for $ i \ge 1 $

1) Base case for n=1. (...)

2) Assume that equation is true for n=k. (...)

3) Proof for n=k+1.
1+2+3+...+k+(k+1) = $ \frac {(k+1)[(k+1)+1]}{2} $

So we add +1 to k on both sides.

For inequalities:
Prove that $ 4n \lt 2^n $ is valid for $ n \ge 5 $

1) Base case. (...)

2) n=k assumption. (...)

3) n=k+1 proof.

How I would do this(add 1 to k on both sides):
$ 4(k+1) < 2^{k+1} $

How it's done in tutorials:
$ 4(k+1) < 2^k + 4 $
$ 4k+4 < 2^k + 4 $

Why they add extra 4 to RHS instead of increasing k by 1?

Answer 1

I think you've got the logic wrong with respect to proof by induction. Let's say we are trying to prove a proposition $P(n)$, which might be, for example, $$P(n): \;1 + 2 + 3 +\cdots + n = \frac{n(n+1)}{2}, \;n\geq 1$$

• Base CaseProve that $P(1)$ is true. That is, we test whether the proposition holds for smallest applicable value of $n$, which in this case is $n = 1.$ This certainly holds, since $1 = \frac{1\cdot 2}{2}$.

• Inductive hypothesis (IH): We assume $P(k)$ holds, i.e. that the proposition holds for $n = k$. So we assume $$P(k):\;1 + 2 + \cdots + k = \dfrac{k(k+1)}{2}$$

• Inductive Step: Now, given that we have assumed that $P(k)$ is true, we need to prove that $P(k)$ implies $P(k+1)$. $P(k+1)$ is not an assumption. We need to prove that it follows from the Inductive Hypothesis (IH). So what we want to prove is that $$1 + 2 + \cdots + k + (k+1) = \dfrac{(k+1)((k+1) + 1)}2 = \dfrac{(k+1)(k+2)}{2}$$We can prove this by starting with what we know and what we have already assumed.$$\color{blue}{1 + 2 + \cdots + k} + (k+1) \overset{IH} = \color{blue}{\frac{k(k+1)}2} + k+1$$ Now, with a little algebra, we can express the right-hand side in the desired form.

---

Now, for the inequality:

Your base case is $n = 5$. Why?

The inductive hypothesis that we assume for $n = k$ is $4k \lt 2^k$.

Now, assuming $4k\lt 2^k$, we need to prove that $4(k+1) \lt 2^{k+1}$. We can start from the left hand side and sue the inductive hypothest:

$$4(k + 1) = \color{blue}{4k} + 4 \lt \color{blue}{2^k} + 4 = 2^k + 2^2 \leq 2\cdot 2^k = 2^{k+1}$$ as desired. The last step on the right holds for $k\geq 2$, which is fine, since we are proving the proposition for $n \geq 5$.

Answer 2

For the first part, you haven't done anything, you just rewrote everything. Most importantly, you didn't prove the statement. Induction works by first showing that $P(1)$ holds then assuming $P(n)$ and proving $P(n+1)$. From there, it follows that the $n$ such that $P(n)$ is true must be all of $\mathbf{N}$.

In our case $P(n)$ is the statement that $1+2+\dots+n=\frac{n(n+1)}{2}$. If we look at $n=1$, we see that $\frac{n(n+1)}{2}=\frac{1\cdot 2}{2}=1$. So that $P(1)$ holds.

Now, we let $n$ be such that $P(n)$ holds and prove that $P(n+1)$ must also be true. Let's consider $1+2+\dots+n+(n+1).$ Recall that we know $P(n)$ is true, so, we can substitute $\frac{n(n+1)}{2}$ in for $1+\dots+n$. Therefore, $$1+2+\dots+n+(n+1)=\frac{n(n+1)}{2}+n+1=\frac{n^2+n+2n+2}{2}=\frac{(n+1)((n+1)+1)}{2}.$$ Notice that the far right hand side is exactly what we wanted to show, that is, that $P(n+1)$ holds.

So, we've shown that the set of $n$ such that $P(n)$ holds is all of $\mathbf{N}$, that is, all $n\geq 1$.

---

Now, for the second question. We let $Q(n)$ be the statement $4n<2^n$ for $n\geq 5$ (I'm assuming yours is a typo, clearly $8=4\cdot 2< 2^2=4$ is not true.)

So, let's do the base case: $2^5=32$ and $4\cdot 5=20$ so clearly we have $4\cdot 5< 2^5$. Thus, $Q(5)$ is true.

Now, let $n$ be such that $Q(n)$ holds. We show that $Q(n+1)$ holds too. Observe that $4(n+1)=4n+4<2^n+4$ by the assumption. However, let's recall that $4=2^2<2^n$ for $n> 2$. Therefore, $$4(n+1)<2^n+2^n=2(2^n)=2^{n+1}.$$

Notice that we've only shown that $Q(n)$ implies $Q(n+1)$ when $n>2$. But, since $5>2$, it follows that $Q(n)$ is true for all $n\geq 5$. Which is exactly what we wanted to show.

Hopefully this helps.