2
$\begingroup$

Use Principle of Mathematical Induction to show that, for every integer $n\ge2$, $$\sum_{{a_{n-1}}=1}^{a_n}\,\sum_{a_{n-2}=1}^{a_{n-1}}\,\ldots\,\sum_{a_{1}=1}^{a_2}\,a_1=\frac{\prod\limits_{i=0}^{n-1}\,(a_n+i)}{n!}\,.$$

I have totally no idea to deal with the product. I can understand it when it only uses 3 sigma notation.

$\endgroup$
5
  • $\begingroup$ any hint will be thankful $\endgroup$ Commented Nov 19, 2018 at 13:12
  • $\begingroup$ Could anyone check whether it is correct? $\endgroup$ Commented Nov 19, 2018 at 13:14
  • $\begingroup$ I think one of the components of PMI lies on whether n=1 is satisfied, your lhs doesnt work on it , so no point in applying .For n>=2 this identity holds true ,I can prove it but not using PMI $\endgroup$
    – swapedoc
    Commented Nov 19, 2018 at 13:30
  • $\begingroup$ @swapedoc How to prove it without PMI? Could you give me a hint? That may help. $\endgroup$ Commented Nov 19, 2018 at 13:32
  • $\begingroup$ hint: look for faulhaber formula , also try to guess coefficients of x^k in (x+1)(x+2)(x+3)....(x+n) where k can be from 0 to n $\endgroup$
    – swapedoc
    Commented Nov 19, 2018 at 13:41

1 Answer 1

1
$\begingroup$

The correct statement is $$\sum_{{a_{n-1}}=1}^{a_n}\,\sum_{a_{n-2}=1}^{a_{n-1}}\,\ldots\,\sum_{a_{1}=1}^{a_2}\,a_1=\frac{\prod\limits_{i=0}^{n-1}\,(a_n+i)}{n!}\text{ for all }n\in\mathbb{Z}_{>0}\text{ and }a_n\in\mathbb{Z}_{\geq 0}\,.$$ This is equivalent to saying that $$\sum_{{a_{n-1}}=1}^{m}\,\sum_{a_{n-2}=1}^{a_{n-1}}\,\ldots\,\sum_{a_{1}=1}^{a_2}\,a_1=\binom{m+n-1}{n}\text{ for all }m\in\mathbb{Z}_{\geq 0}\text{ and }n\in\mathbb{Z}_{>0}\,.\tag{*}$$ To prove by induction, you can justify the Hockey-Stick Identity $$\sum_{k=1}^N\,\binom{k}{r}=\binom{N+1}{r+1}\text{ for all }N,r\in\mathbb{Z}_{\geq 0}\,.\tag{#}$$ (Therefore, if you want to prove everything from the Hockey-Stick Identity to your own identity, then you need two induction proofs. First, prove (#) by induction on $N$. Then prove (*) by induction on $n$.)

Now that I have given a hint on how to do the job inductively, I present a combinatorial approach. Rewrite (*) as $$\sum_{{a_{n-1}}=1}^{m}\,\sum_{a_{n-2}=1}^{a_{n-1}}\,\ldots\,\sum_{a_{1}=1}^{a_2}\,\sum_{a_0=1}^{a_1}\,1=\binom{m+n-1}{n}\text{ for all }m\in\mathbb{Z}_{\geq 0}\text{ and }n\in\mathbb{Z}_{>0}\,.$$ The left-hand side of the equation above counts the number of $n$-tuples $\left(a_0,a_1,a_2,\ldots,a_{n-1}\right)$ of integers $a_0,a_1,a_2,\ldots,a_{n-1}$ such that $$1=:a_{-1}\leq a_0 \leq a_1 \leq a_2\leq \ldots \leq a_{n-1}\leq a_n:=m\,.$$ Let $x_j:=a_j-a_{j-1}$ for $j=0,1,2,\ldots,n$. Then, $(x_0,x_1,x_2,\ldots,x_n)$ is an $(n+1)$-tuple of nonnegative integers such that $$x_0+x_1+x_2+\ldots+x_n=m-1\,.$$ (We can get $a_0,a_1,a_2,\ldots,a_{n-1}$ back by noting that $a_j=1+x_0+x_1+\ldots+x_j$ for every $j=0,1,2,\ldots,n-1$. By the stars-and-bars technique, there are precisely $$\binom{(m-1)+(n+1)-1}{(n+1)-1}=\binom{m+n-1}{n}$$ solutions $(x_0,x_1,\ldots,x_n)$. This proves (*).

$\endgroup$
5
  • $\begingroup$ if I want to do it for every a belongs to Real Number, I cannot use the identities above. $\endgroup$ Commented Nov 27, 2018 at 10:13
  • 2
    $\begingroup$ How are you going to take the sum if the variables are not integers? This has to be specified. $\endgroup$ Commented Nov 27, 2018 at 10:21
  • 2
    $\begingroup$ And how are you going to use induction in nonintegral cases? $\endgroup$ Commented Nov 27, 2018 at 10:23
  • $\begingroup$ if I replace the a1 by f(a1), it also can do the sum. $\endgroup$ Commented Nov 27, 2018 at 10:46
  • 3
    $\begingroup$ How does the sum work? And which occurrence of $a_1$ do you replace by $f(a_1)$ (there are two occurrences of $a_1$ in your expression)? I think you better ask a separate question, and be clear what you want. At this moment, you are not making any sense. $\endgroup$ Commented Nov 27, 2018 at 12:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .