Strong Induction Proof Prove that 
$$\sum_{j=1}^n (j)(j+1)(j+2)\cdots(j+k-1) = \frac{n(n+1)(n+2)\cdots(n+k)}{k+1}$$
Hint:
$P(n, k)$ is true for all pairs of positive integers $n$ and $k$ if:
(a) $P(1, 1)$ is true and $P(n , k) \to [P(n + 1, k) \wedge P(n, k + 1)]$ is true for all positive integers $n$ and $k$.
(b) $P(1, k)$ is true for all positive integers $k$, and $P(n, k) \to P(n + 1, k )$ is true for all positive integers $n$ and $k$.
(c) $P(n, 1)$ is true for all positive integers $n$, and $P(n , k) \to P(n , k + 1)$ is true for all positive integers $n$ and $k$.
I am not sure how to proceed. I can show that $P(1, 1)$ is true and I figure my inductive hypothesis is $P(n , k) \to [P(n + 1, k) \wedge P(n, k + 1)]$ but I am not sure what to do.
 A: The easiest proof, I think, uses the observation that
$$\prod_{i=0}^k(n+i)=\frac{(n+k)!}{(n-1)!}=(k+1)!\cdot\frac{(n+k)!}{(n-1)!(k+1)!}=(k+1)!\binom{n+k}{n-1}\;.$$
Thus,
$$\sum_{j=1}^n\prod_{i=0}^{k-1}(j+i)=\sum_{j=1}^nk!\binom{j+k-1}{j-1}=k!\sum_{j=1}^n\binom{k+j-1}{j-1}=k!\sum_{j=0}^{n-1}\binom{k+j}j\;.$$
Now observe that $\binom{k+j}j=\binom{k+j}k$ and use the well-known ‘hockey-stick' identity,
$$\sum_{j=0}^n\binom{k+j}k=\binom{n+k+1}{k+1}\;,$$
to see that
$$k!\sum_{j=0}^{n-1}\binom{k+j}j=k!\binom{n+k}{k+1}=k!\binom{n+k}{(n+k)-(k+1)}=k!\binom{n+k}{n-1}\;.$$
On the other hand,
$$\frac1{k+1}\prod_{i=0}^k(n+i)=\frac{(k+1)!}{k+1}\binom{n+k}{n-1}=k!\binom{n+k}{n-1}\;,$$
so
$$\sum_{j=1}^n\prod_{i=0}^{k-1}(j+i)=\frac1{k+1}\prod_{i=0}^k(n+i)\;,$$
as desired.
The hockey-stick identity is extremely useful, and you’ll find three different proofs at the link, including a combinatorial proof and a proof by induction.

For the proof by induction that’s suggested in your hint, your induction hypothesis should be $P(n,k)$, i.e., that
$$\sum_{j=1}^n\prod_{i=0}^{k-1}(j+i)=\frac1{k+1}\prod_{i=0}^k(n+i)\;.$$
With this as hypothesis you want to prove both $P(n+1,k)$ and $P(n,k+1)$, i.e., that
$$\sum_{j=1}^{n+1}\prod_{i=0}^{k-1}(j+i)=\frac1{k+1}\prod_{i=0}^k(n+1+i)\tag{1}$$
and that
$$\sum_{j=1}^n\prod_{i=0}^k(j+i)=\frac1{k+2}\prod_{i=0}^{k+1}(n+i)\;.\tag{2}$$
Suppose that you’ve done this, and yet $P(n,k)$ is false for some pair $\langle n,k\rangle$ of positive integers. Let $n$ be the smallest positive integer such that there is a bad pair $\langle n,\ell\rangle$ for some $\ell\in\Bbb Z^+$, and let $k$ be the smallest such $\ell$. Then $P(n,k)$ is false, but $P(m,\ell)$ is true if either $m<n$, or $m=n$ and $\ell<k$. We know that $P(1,1)$ is true, so at least one of $n$ and $k$ is greater than $1$. If $n>1$, then $P(n-1,k)$ is true, and the induction step then shows that $P(n,k)$ is true, contradicting the choice of $n$ and $k$. And if $k>1$, then $P(n,k-1)$ is true, and the induction step again shows that $P(n,k)$ is true, again contradicting the choice of $n$ and $k$. Thus, in every case we reach a contradiction, and it follows that there can be no bad pair $\langle n,k\rangle$; in other words, $P(n,k)$ is true for all positive integers $n$ and $k$.
That gives you the structure of the argument; actually carrying out the induction gets a bit messy. $(1)$ is the easier of the two, and it already takes about as much work as the proof using the hockey-stick identity that I gave at the beginning:
$$\begin{align*}
\sum_{j=1}^{n+1}\prod_{i=0}^{k-1}(j+i)&=\sum_{j=1}^n\prod_{i=0}^{k-1}(j+i)+\prod_{i=0}^{k-1}(n+1+i)&\text{split off last term of sum}\\
&=\frac1{k+1}\prod_{i=0}^k(n+i)+\prod_{i=0}^{k-1}(n+1+i)&\text{induction hypothesis}\\
&=\frac{n}{k+1}\prod_{i=0}^{k-1}(n+1+i)+\prod_{i=0}^{k-1}(n+1+i)\\
&=\left(\frac{n}{k+1}+1\right)\prod_{i=0}^{k-1}(n+1+i)\\
&=\frac{n+1+k}{k+1}\prod_{i=0}^{k-1}(n+1+i)\\
&=\frac1{k+1}\prod_{i=0}^k(n+1+i)\;,
\end{align*}$$
as desired. The third step pulls out the $i=0$ factor, leaving $\prod_{i=1}^k(n+i)$, and then shifts the index down by $1$.
