Question

Prove that$\mathbf{\sum }_{\mathbf{j}\mathbf{=}\mathbf{1}}^{\mathbf{n}}\mathbf{ }\mathit{j}\mathbf{(}\mathit{j}\mathbf{+}\mathbf{1}\mathbf{)}\mathbf{(}\mathit{j}\mathbf{+}\mathbf{2}\mathbf{)}\mathbf{\dots }\mathbf{(}\mathit{j}\mathbf{+}\mathit{k}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{=}\mathit{n}\mathbf{(}\mathit{n}\mathbf{+}\mathbf{1}\mathbf{)}\mathbf{(}\mathit{n}\mathbf{+}\mathbf{2}\mathbf{)}\mathbf{\dots }\mathbf{(}\mathit{n}\mathbf{+}\mathit{k}\mathbf{)}\mathbf{/}\mathbf{(}\mathit{k}\mathbf{+}\mathbf{1}\mathbf{)}$ for all positive integers and . [Hint: Use a technique from Exercise 33.]

Short answer

$\sum _{j=1}^n j(j+1)(j+2)\dots (j+k-1)=n(n+1)(n+2)\dots (n+k)/(k+1)$is true for all positive integersk and n.

Step-by-step solution

Significance of the strong induction

The strong induction is a technique that is different from the simple induction. A strong induction mainly takes lesser time than simple induction to prove a statement or theorem.

Determination of the proof of that statement

Let the statement $P\left(n,k\right)$states that:

$\sum _{j=1}^n j(j+1)(j+2)\dots (j+k-1)=n(n+1)(n+2)\dots (n+k)/(k+1)$ …(i)

In the basis step, $P(1,k)$ holds true for the integers k which are positive. Let the positive integer be k. Then the above equation will be expressed as:

$$\begin{gathered} \sum _{j=1}^n j(j+1)(j+2)\dots ..(j+k-1)=\sum _{j=1}^1 j(j+1)(j+2)\dots .(j+k-1) \\ =1(1+1)(1+2)\dots (1+k-1) \\ =1\left(2\right)\left(3\right)\dots \left(k\right) \end{gathered}$$

Hence, further as.

$$\begin{gathered} \frac{n(n+1)(n+2)\dots (n+k)}{k+1}=\frac{1\left(2\right)\left(3\right)\dots (k+1)}{k+1} \\ =1\left(2\right)\left(3\right)\dots \left(k\right) \end{gathered}$$

Hence, the statement $\sum _{j=1}^n j(j+1)(j+2)\dots .(j+k-1)=n(n+1)(n+2)\dots (n+k)/(k+1)$is proved and $P(1,k)$ holds true.

In the inductive step, let $P(n,k)$holds true. It is needed to be proved that $P(n+1,k)$holds true. Then the equation (i) is expressed as:

$$\begin{gathered} \sum _{j=1}^n j(j+1)(j+2)\dots (j+k-1) \\ =\left(\sum _{j=1}^n j(j+1)(j+2)\dots .(j+k-1)\right)+(n+1)(n+2)(n+3)\dots (n+1+k-1) \end{gathered}$$

As $P\left(k\right)$holds true, then the above equation is expressed as:

$\frac{n(n+1)(n+2)\dots (n+k)}{k+1}+(n+1)(n+2)\dots (n+k)$

In the distributive property,