2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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