Question

Prove by mathematical induction that: Where "E" is the summation icon.

n i
E E j = 1/6n(n+1)(n+2)
i = 1 j=1

Answer 1

Answer to the Question #88204 – Math – Discrete Mathematics

Question

Prove by mathematical induction that: Where "E" is the summation icon.

n i

E E j = 1/6n(n+1)(n+2)

i = 1 j=1

Solution

We want to show by induction that for every positive integer $n \geq 1$ we have

$$\sum_{i=1}^{n} \sum_{j=1}^{i} j = \frac{n(n+1)(n+2)}{6}.$$

This identity holds for $n = 1$ since $\sum_{i=1}^{1} \sum_{j=1}^{i} j = 1 = \frac{6}{6} = \frac{1(1+1)(1+2)}{6}$.

Suppose that for the positive integer $n = k \geq 1$ we have

$$\sum_{i=1}^{k} \sum_{j=1}^{i} j = \frac{k(k+1)(k+2)}{6}.$$

Now, for $n = k + 1$ we have

$$\sum_{i=1}^{k+1} \sum_{j=1}^{i} j = \sum_{i=1}^{k} \sum_{j=1}^{i} j + \sum_{j=1}^{k+1} j.$$

By applying the induction hypothesis and noting the fact that $\sum_{i=1}^{r} i = \frac{r(r+1)}{2}$, we conclude that

$$\sum_{i=1}^{k+1} \sum_{j=1}^{i} j = \frac{k(k+1)(k+2)}{6} + \frac{(k+1)(k+2)}{2} = \frac{(k+1)((k+1)+1)((k+1)+2)}{6}.$$

Thus, it has been proved by induction that the identity holds for every integer

$n \geq 1$.

Q.E.D.

Answer provided by https://www.AssignmentExpert.com