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
(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.
