3
$\begingroup$

This is from this website:

Use mathematical induction to prove that $$1 + 2 + 3 +\cdots+ n = \frac{n (n + 1)}{2}$$ for all positive integers $n$.

Solution to Problem 1: Let the statement $P(n)$ be $$1 + 2 + 3 + \cdots + n = \frac{n (n + 1)}{2}.$$

STEP 1: We first show that $P(1)$ is true.

Left Side $= 1$

Right Side $= \frac{1 (1 + 1)}{2} = 1$

Both sides of the statement are equal hence $P(1)$ is true.

STEP 2: We now assume that $P(k)$ is true
$$1 + 2 + 3 + \cdots + k = \frac{k (k + 1)}{2}$$ and show that $P(k + 1)$ is true by adding $k + 1$ to both sides of the above statement $$ \begin{align} 1 + 2 + 3 + \cdots + k + (k + 1) &= \frac{k (k + 1)}{2} + (k + 1) \\ &= (k + 1)\left(\frac{k}{2} + 1\right) \\ &= \frac{(k + 1)(k + 2)}{2} \end{align} $$ The last statement may be written as $$1 + 2 + 3 + \cdots + k + (k + 1) = \frac{(k + 1)(k + 2)}{2}$$ Which is the statement $P(k + 1)$.

My question is how in the very last line is the statement $P(k + 1)$ equal to $\frac{(k + 1)(k + 2)}{2}$. I don't get the last step.

$\endgroup$
  • $\begingroup$ Have you used induction before or is this your first time? $\endgroup$ – Daniel W. Farlow Mar 25 '15 at 22:00
  • $\begingroup$ Do you understand that $p(k+1) = 1 + 2 + 3 + \cdots + k + (k+1)$? $\endgroup$ – user137731 Mar 25 '15 at 22:05
  • 1
    $\begingroup$ crash:This is my first time $\endgroup$ – Sam Lot Mar 25 '15 at 22:12
  • $\begingroup$ Bye_world:i understand that we are adding k + 1 to both sides in p(k+1)=1+2+3+⋯+k+(k+1) $\endgroup$ – Sam Lot Mar 25 '15 at 22:13
6
$\begingroup$

Since this is your first time, I'll try to explain it with an emphasis on clarity. If something isn't clear, just comment and I'll try to explain what's happening.

Claim: You are trying to prove the statement $P(n)$ where $$ P(n) : 1+2+3+\cdots+n = \frac{n(n+1)}{2}. $$ Your goal is to try to prove this using induction. Proofs by induction usually involve two things: (1) showing that $P(n)$ is true for some fixed value of $n$; this value is oftentimes $n=1$, as it is in your case since you are trying to prove $P(n)$ for all $n\geq 1$. Make sense so far? (2) After you have shown (1) to be true, you then need to assume $P(k)$ to be true for some fixed $k\geq 1$ and then show that $P(k)$ implies $P(k+1)$; that is, you need to show that "if $P(k)$ is true, then $P(k+1)$ is true."

  • (1) is called the base case.
  • (2) is called the inductive step.

I'll outline the proof below. Let me know if a step doesn't make sense.

Proof. Let $P(n)$ denote the statement $$ P(n) : 1+2+3+\cdots+n = \frac{n(n+1)}{2}. $$ Base case ($n=1$): Try to see what happens for $P(1)$. We get that $1 = \frac{1(1+1)}{2}$, and this is true. Thus, the base case holds for $n=1$. Inductive step ($P(k)\to P(k+1)$): Assume $P(k)$ is true for some fixed $k\geq 1$ (this is called the inductive hypothesis). That is, assume $$ P(k) : \color{red}{1+2+3+\cdots+k} = \color{green}{\frac{k(k+1)}{2}}\tag{inductive hypothesis} $$ is true. We must show that $P(k+1)$ follows where $$ P(k+1) : \underbrace{\color{red}{1+2+3+\cdots+k}+\color{blue}{(k+1)}}_{\text{LHS or "left-hand side"}} = \underbrace{\color{purple}{\frac{(k+1)((k+1)+1)}{2}}}_{\text{RHS or "right-hand side"}}. $$


Side note: Make sure you understand what just happened with $P(k+1)$. For $P(k)$, we just had $1+2+3+\cdots+k$ on the left-hand side. How come we have $1+2+3+\cdots+k+(k+1)$ now for the left-hand side of $P(k+1)$? This is because we are adding another term to the sum, namely $k+1$ (I highlighted this term with blue). On the right-hand side, where $P(k)$ just had $k$ in its expression, we just replace all of those $k$'s with $k+1$ because we are considering $P(k+1)$. Make sense?


Okay. Starting with the left-hand side of $P(k+1)$, we need to show that the right-hand side of $P(k+1)$ follows. Here's how it works: \begin{align} \text{LHS} &= \color{red}{1+2+3+\cdots+k}+\color{blue}{(k+1)}\tag{by definition}\\[1em] &= \color{green}{\frac{k(k+1)}{2}}+\color{blue}{(k+1)}\tag{by inductive hypothesis}\\[1em] &= \frac{\color{green}{k(k+1)}+\color{green}{2}\color{blue}{(k+1)}}{\color{green}{2}}\tag{common denominator}\\[1em] &= \frac{(k+1)\color{green}{(k+2)}}{\color{green}{2}}\tag{group like terms}\\[1em] &= \color{purple}{\frac{(k+1)((k+1)+1)}{2}}\tag{rearrange}\\[1em] &= \text{RHS} \end{align} Thus, we have shown that the right-hand side of $P(k+1)$ follows from the left-hand side of $P(k+1)$. This completes the inductive step.

Thus, by mathematical induction, the statement $P(n)$ is true for all $n\geq 1$. $\blacksquare$

Does it all make sense now?

$\endgroup$
  • $\begingroup$ What does P in P(n) stand for ? Proof ? $\endgroup$ – Sam Lot Mar 25 '15 at 23:05
  • $\begingroup$ @SamLot No. $P$ just indicates a statement. I could have used $S(n)$ or $R(n)$ or anything else for that matter. $\endgroup$ – Daniel W. Farlow Mar 25 '15 at 23:06
  • $\begingroup$ In the inductive step ,what does this "(P(k)→P(k+1))" means ? $\endgroup$ – Sam Lot Mar 25 '15 at 23:08
  • $\begingroup$ @SamLot It means "$P(k)$ implies $P(k+1)$." The "$\to$" symbol is a mathematical symbol for "implies." $\endgroup$ – Daniel W. Farlow Mar 25 '15 at 23:09
  • $\begingroup$ It makes more sense now .Thanks $\endgroup$ – Sam Lot Mar 25 '15 at 23:16
2
$\begingroup$

We know that

$P(k) = 1 + 2 + 3 + ... + k$

Therefore:

$P(k+1) = 1 + 2 + 3 + ... + k + (k+1)$

By induction hypothesis we have:

$1 + 2 + 3 + ... + k + (k+1) = \frac{(k+1)(k+2)}{2}$

so

$P(k+1) = 1 + 2 + 3+...+k+(k+1) = \frac{(k+1)(k+2)}{2}$

so

$P(k+1) = \frac{(k+1)(k+2)}{2}$

By induction we now know that since this is true for one integer $k$, it is true for all integers greater than or equal to $k$.

$\endgroup$
  • $\begingroup$ Rather that "we already proved that $1 + 2 + 3 + ... + k + (k+1) = \frac{(k+1)(k+2)}{2}$" I would say "By induction hypothesis it is $1 + 2 + 3 + ... + k + (k+1) = \frac{(k+1)(k+2)}{2}$". Note that it was not proved. $\endgroup$ – mfl Mar 25 '15 at 22:15
  • $\begingroup$ How can we say in the first line that "We know that P(k)=1+2+3+...+k" Where did that come from .Secondly how does the formula in last line P(k+1)=(k+1)(k+2)2 prove that 1+2+3+...+n=n(n+1)2 .How can i link them ? $\endgroup$ – Sam Lot Mar 25 '15 at 22:27
  • $\begingroup$ In the problem $P(n)$ is defined as $1+2+3+...+n$. $P(k+1) = \frac{(k+1)(k+2)}{2}$ proves that $P(k) = \frac{(k)(k+2)}{2}$ because we have shown that it is true for $1$. Say that $k=1$. We know from these formulas that if the statement is true for a number $k$ it is true for $k+1$. Since it is true for $k+1$, it must be true for $(k+1)+1$ and so on and so on. $\endgroup$ – OriginalOldMan Mar 25 '15 at 22:33
  • $\begingroup$ When you say "We know that P(k)=1+2+3+...+k Therefore: P(k+1)=1+2+3+...+k+(k+1)" in the last line here you are adding 1 to the left side and k + 1 to the right side .Isnt that mathematically incorrect ? $\endgroup$ – Sam Lot Mar 25 '15 at 22:40
  • $\begingroup$ We are not adding $1$ to both sides. $P(k)$ is basically the sum of integers from $1$ to $k$. So $P(k+1)$ is the sum of integers from $1$ to $(k+1)$. $k$ is obviously the integer before $(k+1)$. So the sum of integers from $1$ to $(k+1)$ is $1+2+3+...+k+(k+1)$. That's why we can say that $P(k+1) = 1+2+3+...+k+(k+1)$. $\endgroup$ – OriginalOldMan Mar 25 '15 at 22:44
1
$\begingroup$

induction is basically saying that if it is true for this step, it is true for the next step. so assuming $1+2+3...+k=k(k+1)/2$, ie it is true for step k, we have to show that it must be true for step k+1, the next step. the final line shows how, by going through some algebra, adding all the numbers up to k+1 equals putting k+1 into the formula $n(n+1)/2$, written as $1+2+3...+k+[k+1]=[k+1]([k+1]+1)/2$. therefore, if it is true for step 1, it is for step 2, and 3...

$\endgroup$
  • $\begingroup$ I dont understand this part from your explanation "adding all the numbers up to k+1 equals putting k+1 into the formula n(n+1)/2".How does those two things 'equal' each other ? $\endgroup$ – Sam Lot Mar 25 '15 at 22:20
  • $\begingroup$ you show that they equal each other with the algebra: $\endgroup$ – stanley dodds Mar 26 '15 at 7:00
  • $\begingroup$ $1+2+3...+k=\frac{k(k+1)}2$, the initial statement. add k+1: $\endgroup$ – stanley dodds Mar 26 '15 at 7:03
  • $\begingroup$ $1+2+3...+k+[k+1]=\frac{k(k+1)}2+k+1$. then rearrange the rhs: $\endgroup$ – stanley dodds Mar 26 '15 at 7:06
  • 1
    $\begingroup$ multiply on rhs: $=\frac{(k+1)(k+2)}2$ which could also be written as $\frac{[k+1]([k+1]+1)}2$. this is the initially presumed equation for k+1, so with. algebra we have shown that if it works for k it works for k+1, and then if it works for that step it works for the next step, and so on $\endgroup$ – stanley dodds Mar 26 '15 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.