2
$\begingroup$

Use any method to prove that $$\binom{n+1+m}{n+1}=\sum_{k=0}^m(k+1)\binom{n+m-k}{n}$$

My Try:

Base case: Let $m=1$

LHS$$\binom{n+1+m}{n+1}=\binom{n+2}{n+1}=(n+2)$$ RHS$$\sum_{k=0}^m(k+1)\binom{n+m-k}{n}=\binom{n+1-0}{n}+(1+1)\binom{n+1-1}{n}$$ $$=\frac{(n+1)!}{n!}+2$$ $$=(n+3)$$

If $m=2$

LHS$$\binom{n+3}{n+1}=\frac{n^2+5n+6}{2!}$$ RHS$$=\binom{n+2}{n}+2\binom{n+1}{n}+3\binom{n}{n}$$ $$=\frac{n^2+3n+2+4n+4+6}{2}=\frac{n^2+7n+12}{2}$$

Clearly $LHS\ne RHS$

If LHS and RHS are not equal then how to prove this proof? Can anyone explain how to prove this.

$\endgroup$
  • 4
    $\begingroup$ If something is not true, you cannot prove that it is true. $\endgroup$ – Batominovski Dec 8 '18 at 16:46
  • $\begingroup$ @Batominovski If it is wrong, then why am I asked to prove the equation. $\endgroup$ – user982787 Dec 8 '18 at 17:23
  • 1
    $\begingroup$ Mistakes happen. I hope you understand that humans are not perfect, regardless of their intelligence and experiences. $\endgroup$ – Batominovski Dec 8 '18 at 17:26
3
$\begingroup$

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{\require{cancel}\bcancel{\cancel{n + 1 + m \choose n + 1}} = \sum_{k = 0}^{m}\pars{k + 1}{n + m - k \choose n}:\ {\LARGE ?}}$.

The right answer is $\bbx{\ds{n + m + 2 \choose n + 2}}$

$$ \bbx{\mbox{Note that}\ {n + m - k \choose n} = 0\ \mbox{when}\ k > m} $$


\begin{align} &\bbox[10px,#ffd]{\sum_{k = 0}^{m}\pars{k + 1} {n + m - k \choose n}} = \sum_{k = 0}^{\infty}\pars{k + 1}{n + m - k \choose m - k} \\[5mm] = &\ \sum_{k = 0}^{\infty}\pars{k + 1} \bracks{{-n - 1 \choose m - k}\pars{-1}^{m - k}} \\[5mm] = &\ \pars{-1}^{m}\sum_{k = 0}^{\infty}\pars{k + 1}\pars{-1}^{k} \bracks{z^{m - k}}\pars{1 + z}^{-n - 1} \\[5mm] = &\ \pars{-1}^{m}\bracks{z^{m}}\pars{1 + z}^{-n - 1} \sum_{k = 0}^{\infty}\pars{k + 1}\pars{-z}^{k} \\[5mm] = &\ \pars{-1}^{m}\bracks{z^{m}}\pars{1 + z}^{-n - 1}\, \pars{-\,\partiald{}{z}\sum_{k = 0}^{\infty}\pars{-z}^{k + 1}} \\[5mm] = &\ \pars{-1}^{m}\bracks{z^{m}}\pars{1 + z}^{-n - 1}\, \partiald{}{z}\pars{z \over 1 + z} = \pars{-1}^{m}\bracks{z^{m}}\pars{1 + z}^{-n - 3} \\[5mm] = &\ \pars{-1}^{m}{-n - 3 \choose m} = \pars{-1}^{m}\bracks{{n + 3 + m - 1\choose m}\pars{-1}^{m}} \\[5mm] = &\ \bbx{n + m + 2 \choose n + 2} \end{align}

$\endgroup$
2
$\begingroup$

The RHS can be written as $$\sum_{i+j=n+m+1}\binom{i}1\binom{j}n$$where $\binom{r}{s}:=0$ if $s\notin\{0,\dots,r\}$.

This equals: $$\binom{n+2+m}{n+2}$$ See here for a proof of that. So RHS does not equal LHS.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.