1
$\begingroup$

I'm attempting to prove the following.

Prove that $2\times (1+2+...+n) = n \times (n+1) $ for all natural numbers $n$.

We're only allowed the use of Peano's axioms and the induction method to solve this proof. I've shown the basis step of the induction easy enough.

Assume $n=1$ and $S(n)$ defines the successor of $n$. Then, $$ 2 \times (1) = 1 \times (1+1) \\ 2 = 1 \times S(1) \\ 2 = S(1) $$

My problem is proving this is true for all $n$. We know that by Peano's second axiom, $n$ must have a successor $S(n)$. We can then say that

$$ 2 \times (1+2+...+n+S(n)) = S(n) \times (S(n)+1) $$

From here, I began operating on the right-hand side in an attempt to find the left-hand side. But, I keep finding myself going in circles with the algebra. I've tried this problem 4 different ways and cannot seem to find where to use the induction hypothesis that allows me to finish the proof.

Any hints would be greatly appreciated, thank you.

$\endgroup$
  • 1
    $\begingroup$ Don't really know how formal you are trying to get, but $a + 1 = S(a)$, can you prove this? Then, how can split up $2 \times (1 + 2 + \ldots + n + S(n))$? Using induction, what can you assume about what you split up? $\endgroup$ – Dair Jan 17 '17 at 1:03
  • $\begingroup$ @Dair In a different problem, I did prove $a+1=S(a)$. Are you referring to $2 \times (1 + 2+... + n + n+1)$? I also said that $2 = S(1)$, but I'm not sure how to tie those two together to give me the RHS of the equation. $\endgroup$ – Kosta Jan 17 '17 at 1:07
  • 1
    $\begingroup$ $2 \times (1 + 2 + \ldots + n + S(n)) = 2 \times (1 + 2 + \ldots + n) + 2 \times S(n)$, what can you say about $2 \times (1 + 2 + \ldots + n) $? $\endgroup$ – Dair Jan 17 '17 at 1:09
2
$\begingroup$

You want to prove that, given the proposition $P(n) \equiv 2 \times (1 + 2 + \ldots + n) = n \times (n + 1)$, that you have the inductive step $P(n) \rightarrow P(S(n))$. So, what you want to do, is start from $P(n)$ and manipulate it to look more like $P(S(n))$. So we have:

$$\begin{eqnarray}& 2 \times (1 + 2 + \ldots + n) & = & n \times (n + 1)\\ & 2 \times (1 + 2 + \ldots + n) + 2 \times S(n) & = & n \times (n + 1) + 2 \times S(n) & \mbox{adding S(n)}\\ & 2 \times (1 + 2 + \ldots + n + S(n)) & = & n \times (n + 1) + 2 \times S(n) & \mbox{by associativity}\\ & & = & n \times S(n) + 2 \times S(n) & \mbox{(1)} \\ & & = & (n + 2) \times S(n) & \mbox{distributivity} \end{eqnarray}$$

and from there you should be able to rearrange things as necessary. Note that I'm assuming you already have an appropriate theorem that identifies $n + 1 = S(n)$, which you will have to use again when you complete the proof. Without that, it might be a little trickier.

$\endgroup$
  • $\begingroup$ Oh, duh. So continuing on with the RHS, $(n+S(1)) \times S(n) = (n+1+1) \times S(n) = (S(n)+1) \times S(n)$ So we've shown that the equation also holds true for its successor, therefore the equation is true for all $n$ in the natural numbers. Is this correct? $\endgroup$ – Kosta Jan 17 '17 at 1:34
  • 1
    $\begingroup$ Pretty much. The main things are that you prove $P(0)$, and you prove $P(n) \rightarrow P(S(n))$, and then the Axiom of Induction says that $P(n)$ is true for all $n$ - and you have indeed done so. $\endgroup$ – ConMan Jan 17 '17 at 4:00

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.