# Prove by induction that for all $n\in\Bbb N$. [duplicate]

Can anyone please show me how to solve this problem? I'm stuck $$\sum_{k=1}^n k = \frac{n(n+1)}{2}$$ $$and$$ $$\sum_{k=1}^n k^3 = \left(\sum_{k=1}^n k\right)^2$$

To prove by induction, it has to be as following:
1) Base Case: Show that P(n) is true.
2) Induction Hypothesis: Assume P(k) is true. for $k\in\Bbb N$
3) Induction Step: Show that P(k + $1$) is also true.

## marked as duplicate by Jean Marie, Hans Lundmark, draks ..., user91500, NamasteMay 18 '17 at 11:22

• Your base case should be $P(1)$, not $P(n)$. Actually, could you try some of the steps, maybe you'll just get there, they are not that difficult :) – Yujie Zha May 18 '17 at 4:20
• Rules $(1)$ and $(2)$ that you put down aren't correct. If you want to prove that $P(n)$ is true for all $n \ge n_0$, then $(1)$ should be "show that $P(n_0)$ is true", and $(2)$ should be "assume that $P(k)$ is true for all $n_0 \le k < n$." Then $(3)$ is "show that $P(n)$ is true." – Chris May 18 '17 at 4:22
• First show that P(1) is true. Then show that, for any n, that IF P(n) is true THEN P(n+1) is true. – DanielWainfleet May 18 '17 at 4:39
• Multiple duplicate of (math.stackexchange.com/q/292423) and (math.stackexchange.com/q/973456) ! – Jean Marie May 18 '17 at 5:46

you have the structure right.

I will walk you through one, and leave number 2 to you, and you can use this template

Proposition: $\sum_\limits{k=1}^n k = \frac{n(n+1)}{2}$

base case: $n=1$

$1 = \frac {1(2)}{2}$

Inductive hypothesis: Suppose $P(n)$ is true

We must show that $P(n) \implies P(n+1)$

$\sum_\limits{k=1}^{n+1} k = \left(\sum_\limits{k=1}^{n} k\right) + (n+1)$

$\sum_\limits{k=1}^{n} k = \frac {n(n+1)}{2}$ by the inductive hypothesis.

$\sum_\limits{k=1}^{n+1} k = \frac {n(n+1)}{2} + n+1 = \frac {(n+2)(n+1)}{2}$

QED

The induction step for part $2$ is:

$$\left(\sum_{k=1}^{n+1} k\right)^2=\left(\sum_{k=1}^n k + (n+1)\right)^2$$

$$=(n+1)^2 + 2(n+1)\sum_{k=1}^n k+\left(\sum_{k=1}^n k\right)^2$$

$$=(n+1)^2 + n(n+1)^2+\sum_{k=1}^n k^3$$

$$=(n+1)^3+\sum_{k=1}^n k^3$$

$$=\sum_{k=1}^{n+1} k^3$$