0

If $m, n, p, q$ are non-negative integers prove that

$$\sum^q_{m=0}(n-m)\frac{(p+m)!}{m!}=\frac{(p+q+1)!}{q!}\left(\frac{n}{p+1}-\frac{q}{p+2}\right)$$

TShiong
  • 1,257
Shubhraneel Pal
  • 1,032

2 Answers2

1

Induction on $q$

Induction basis:

for $q=0$, LHS=n.p!=RHS, the equality holds.

Induction hypothesis: for $<=q$ let the equality hold.

Induction step: for $q+1$, let's prove the equality holds.

$\sum \limits _{n=0}^{q+1}(n-m)\frac{(p+m)!}{m!}$ $=\sum \limits _{n=0}^{q}(n-m)\frac{(p+m)!}{m!} + (n-m)\frac{(p+q+1)!}{(q+1)!}$ $=\frac{(p+q+1)!}{q!}\left(\frac{n}{p+1}-\frac{q}{p+2}\right) + (n-(q+1))\frac{(p+q+1)!}{(q+1)!}$ (by induction hypothesis) $=\frac{(p+q+1)!}{q!}\left(\frac{n}{p+1}\right)-\frac{(p+q+1)!}{q!}\left(\frac{q}{p+2}\right) + (n-(q+1))\frac{(p+q+1)!}{(q+1)!}$ $=\frac{(p+q+1)!}{q!}\left(\frac{n}{p+1}\right) + n\frac{(p+q+1)!}{(q+1)!}-\frac{(p+q+1)!}{q!}\left(\frac{q}{p+2}\right) - (q+1)\frac{(p+q+1)!}{(q+1)!}$ $=\frac{(p+q+1)!n}{(p+1)(q+1)!}\left((q+1)+(p+1)\right) -\frac{(p+q+1)!}{(p+2)q!}\left(q+ (p+2)\right)$ $=\frac{(p+q+1)!n}{(p+1)(q+1)!}\left(p+q+2\right) -\frac{(p+q+1)!}{(p+2)q!}\left(p+q+2\right)$ $=\frac{(p+q+2)!n}{(p+1)(q+1)!}-\frac{(p+q+2)!}{(p+2)q!}$

$=\frac{(p+(q+1)+1)!}{(q+1)!}\left(\frac{n}{p+1}-\frac{q+1}{p+2}\right)$ (Proved)

Sandipan Dey
  • 2,111
  • How to know which variable to induce in these types of problems? – Shubhraneel Pal Dec 24 '16 at 16:10
  • 1
    RHS contains 3 variables $p, q, n$ but does not contain $m$, the quantity that varies on LHS is the upper bound of the variable $m$ to be summed on, which is $q$. Hence, $q$ is the variable to induct on. – Sandipan Dey Dec 24 '16 at 16:15
1

The induction step becomes proving that $$ \frac{(p+q+1)!}{q!}\left(\frac{n}{p+1}-\frac{q}{p+2}\right)+ (n-q-1)\frac{(p+q+1)!}{(q+1)!}= \frac{(p+q+2)!}{(q+1)!}\left(\frac{n}{p+1}-\frac{q+1}{p+2}\right) $$ In the left-hand side we can collect $$ \frac{(p+q+1)!}{q!} $$ so it becomes $$ \frac{(p+q+1)!}{q!} \left( \frac{n}{p+1}-\frac{q}{p+2}+\frac{n-q-1}{q+1} \right)\tag{*} $$ Let's consider only the expression in parentheses: $$ \frac{n}{p+1}-\frac{q}{p+2}+\frac{n-q-1}{q+1}= \frac{n}{p+1}+\frac{n}{q+1}-\frac{q}{p+2}-1= \frac{n(p+q+2)}{(p+1)(q+1)}-\frac{p+q+2}{p+2} $$ Collect $p+q+2$ to get $$ (p+q+2)\left(\frac{n}{(p+1)(q+1)}-\frac{q+1}{(p+2)(q+1)}\right) $$ Now…

egreg
  • 238,574