Prove by Induction with Summation

Question

Struggling with this , especially with the double summation; if anyone can help it be much appreciated!

$$\forall n \in \Bbb N : \quad \sum_{i=1}^n \sum_{c=1}^i c = \sum_{i=1}^n i(n − i + 1) .$$

It needs to be answered in the following format:

1- Prove for n=1

2- assume n=k

3- prove for k+1

Answer 1

If you make a drawing in the plane of the couples $(i,c)$ that are being considered in the LHS sum, you'll see a triangle with apexes $(1,1)$, $(n,1)$ and $(n,n)$. In this triangle, you count the $c$'s vertically.

Here is a visualization of what is happening:

Now switch the two sums, using your drawing : $$\sum_{i=1}^n \sum_{c=1}^i c = \sum_{c=1}^n \sum_{i=c}^n c$$ but in the inner RHS sum, $c$ is a constant, and there are $n-c+1$ terms. So : $$\sum_{c=1}^n \sum_{i=c}^n c = \sum_{c=1}^n c(n-c+1)$$ All that is left is to rename $c$ as $i$ :-)

I'd like to include the drawing, but don't know how to do. Maybe Tikz is implemented ?

Answer 2

$$\begin{align} \sum_{i=1}^n \sum_{c=1}^i c &= \sum_{c=1}^n \sum_{i=c}^n c\qquad (1\le c\le i\le n)\\ &= \sum_{c=1}^n c\sum_{i=c}^n 1\\ &=\sum_{c=1}^n c(n-c+1)\\ &=\sum_{i=1}^n i(n − i + 1) \end{align}$$

Answer 3

Rewrite the identity for $n+1$:

• Left hand side $$\sum_{i=1}^{n+1} \sum_{c=1}^i c =\sum_{i=1}^{n} \sum_{c=1}^i c+\sum_{c=1}^{n+1} c.$$

• Right hand side $$\sum_{i=1}^{n+1} i(n+1 − i + 1)=\sum_{i=1}^{n+1} i(n− i + 1)+\sum_{i=1}^{n+1}i=\sum_{i=1}^{n} i(n− i + 1)+\sum_{i=1}^{n+1}i.$$

As the additional terms are the same, if the identity holds for $n$, then it holds for $n+1$.

Answer 4

Here is an answer based upon induction. We show:

The following is valid \begin{align*} \sum_{i=1}^n \sum_{c=1}^i c = \sum_{i=1}^n i(n - i + 1)\qquad\qquad n\geq 1 \end{align*}

Base step: $n=1$

We have to show \begin{align*} \sum_{i=1}^1 \sum_{c=1}^i c = \sum_{i=1}^1 i(1 - i + 1) \end{align*}

Since \begin{align*} \text{LHS: }\qquad&\sum_{i=1}^1 \sum_{c=1}^i c =\sum_{c=1}^1 c=1\\ \text{RHS: }\qquad&\sum_{i=1}^1 i(1 - i + 1)=1\cdot(1-1+1)=1 \end{align*}

the claim is valid for $n=1$.

Induction hypothesis: $n=k$

We assume the validity of \begin{align*} \sum_{i=1}^k \sum_{c=1}^i c = \sum_{i=1}^k i(k - i + 1)\tag{1} \end{align*}

Induction step: $n=k+1$

We have to show \begin{align*} \sum_{i=1}^{k+1} \sum_{c=1}^i c = \sum_{i=1}^{k+1} i(k - i + 2) \end{align*}

We obtain \begin{align*} \sum_{i=1}^{k+1} \sum_{c=1}^i c&=\sum_{i=1}^{k} \sum_{c=1}^i c+\sum_{c=1}^{k+1} c\tag{2}\\ &=\sum_{i=1}^{k} i(k - i + 1)+\sum_{c=1}^{k+1} c\tag{3}\\ &=\sum_{i=1}^{k+1} i(k - i + 1)+\sum_{c=1}^{k+1} c\tag{4}\\ &=\sum_{i=1}^{k+1} i(k - i + 1)+\sum_{i=1}^{k+1} i\tag{5}\\ &=\sum_{i=1}^{k+1} i(k - i + 2)\tag{6}\\ \end{align*} and the claim follows.

Comment:

• In (2) we separate the summand with index $i=k+1$.

• In (3) we apply the induction hypothesis (1).

• In (4) we set the upper limit of the left sum to $k+1$ without changing anything since we are adding zero only.

• In (5) we change the name of the index $c$ to $i$ in the second sum.

• In (6) we merge the second sum into the first one.