3

Im just confused by this equation and how it was used.

Assume

$$P(n) = 1 + 2 + 3 + 4 + \cdots + n = \frac{n(n+1)}2$$ Inductive step

$$P(n+1) = 1 + 2 + 3 + 4 + \cdots + n + (n+1) = \frac{(n+1)(n+2)}2$$

Why is the inductive step not written like this?

$$P(n+1) = 1 + 2 + 3 + 4 + \cdots + (n+1) = \frac{(n+1)(n+2)}2$$

José Carlos Santos
  • 427,504
John Harold Artista
  • 31
  • 1
  • 1
    They mean the same thing, excluding $n$ in the second line doesn't change anything, since it's still implied its there. Both are 100% okay and mean the same thing. – Patty Jul 19 '17 at 05:20

3 Answers3

4

It's so that it is clear how to use the induction hypothesis. If the $n$ term wasn't visible, it wouldn't be so obvious how to proceed.

José Carlos Santos
  • 427,504
2

There are the same thing. Just because the $n$ isn't visible, doesn't mean that it is not there. Always remember to write the $n$ because you are going to use the statement that holds for a fixed $n$, by assumption, to prove that this implies that the given statement is true for the integer $n+1$.

I hope this helps you!

math_guy27
  • 453
  • The inductive step is not P(n+n+1) right. So why is it written that way? just confused with that part. 1+2+3+4... n+n+1? – John Harold Artista Jul 19 '17 at 05:37
  • @JohnHaroldArtista no, the inductive step is proving that $P(n)$ implies $P(n+1)$. That is, assume that $P(n)$ is true and with this assumption, prove that $P(n+1)$ is also true. – math_guy27 Jul 19 '17 at 05:43
2

You assume that $P(n)$ is true and prove that $P(n+1)$ is also true from that.

So assume $1+2+3+\cdots+n=\frac {n(n+1)}2$.

Then from this we get $1+2+3+\cdots+n+(n+1)=\frac {n(n+1)}2 + (n+1)=(n+1)(\frac n2+1)=\frac {(n+1)(n+2)}2.$(Which the answer has avoided to mention here)

This is exactly what is done in that step you have stumbled upon. That's why writing the "$n$" matters in $1+2+3+\cdots+n+(n+1)$. Because you are using trueness of $P(n)$ here to show trueness of $P(n+1)$.

Error 404
  • 6,006