<s>[INST] Binomial coefficients (Concrete mathematics 5.39) 
Show that if $xy = ax+by$ then $$x^ny^n = \sum_{k=1}^n \binom{2n-1-k}{n-1} (a^nb^{n-k}x^k + a^{n-k}b^ny^k)$$ for all $n>0$. Find a similar formula for the more general product $x^my^n$. (There formulas give useful partial fraction expansions, for example when $x=1/(z-c)$ and $y=1/(z-d)$.)

I have no idea what I could do with this problem. I tried to substitute, but failed..
Hope someone can help
 [/INST] (a) We prove it by induction. Initial case, $n=1$:
\begin{align}
\sum_{k=1}^n{\binom{2n-1-k}{n-1} (a^nb^{n-k}x^k + a^{n-k}b^ny^k)} & = \binom{0}{0}(a^1b^0x^1 + a^ob^1y^1) \\
& = ax+by \\
& = x^ny^n.\qquad\checkmark
\end{align}
Now assume the statement is true for some $n\gt 0$ and consider the case for $n+1$.
\begin{align}
(xy)^{n+1} & = (ax+by) x^ny^n \\
(xy)^{n+1} & = (ax+by) \sum_{k=1}^n{\binom{2n-1-k}{n-1} (a^nb^{n-k}x^k + a^{n-k}b^ny^k)} \qquad\text{by inductive assumption} \\
& = \sum_{k=1}^n{\binom{2n-1-k}{n-1} (a^{n+1}b^{n-k}x^{k+1} + a^{n-k}b^{n+1}y^{k+1} + a^nb^{n-k+1}x^ky + a^{n-k+1}b^ny^kx)} 
\end{align}
We have a term in $x^ky$ that we need to convert to an expression with $x$ and $y$ separated.
\begin{align}
x^ky & = x^{k-1}(ax+by) \\
& = ax^k + bx^{k-1}y \\
& = ax^k + bx^{k-2}(ax+by) \\
& = ax^k + abx^{k-1} + b^2x^{k-2}y \\
& = \cdots \\
& =  ax^k + abx^{k-1} + ab^2x^{k-2} + \cdots + ab^{k-1}x + b^ky.
\end{align}
The $y^kx$ term can be similarly expanded.
Then for any $j=1,\ldots ,n+1$ the $x^j$ term in the above summation has the following components:
\begin{align}
\text{For } k & =j-1: & \ \qquad \binom{2n-j}{n-1} a^{n+1}b^{n-j+1}x^j \\
k & =j: & \ \qquad \binom{2n-1-j}{n-1} a^{n+1}b^{n-j+1}x^j \\
k & =j+1: & \ \qquad \binom{2n-2-j}{n-1} a^{n+1}b^{n-j+1}x^j \\
& \ \ldots & \\
k & =n: & \ \qquad \binom{n-1}{n-1} a^{n+1}b^{n-j+1}x^j. \\
\end{align}
Summing these, we get $c_j$, the coefficient of the $x^j$ term:
\begin{align}
c_j & = \sum_{i=0}^{n-j+1}{\binom{2n-j-i}{n-1}} \\
 & = \sum_{i=0}^{n-j+1}{\binom{n-1+i}{n-1}} \qquad\text{reversing the order of summation}\\
& = \binom{2n-j+1}{n} \qquad\text{by Identity 5.9 with $n:=n-j+1,\; r:=n-1$} \\
& = \binom{2(n+1) - 1 - j}{(n+1) - 1}.
\end{align}
Identity 5.9 from Concrete Mathematics can also be found here after Equation 8.
A similar argument works to determine the $y^j$ term and with that we have shown that the statement holds for $n+1$ and the proof is complete.
(b) Some trial and error indicates that the equivalent formula for $x^my^n$ is:
$$x^my^n = \sum_{k=1}^m{\binom{m+n-1-k}{n-1} a^nb^{m-k}x^k} + \sum_{k=1}^n{\binom{m+n-1-k}{m-1} a^{n-k}b^my^k}.$$
I imagine this formula could also be proved by induction.
</s>