A (combinatorial..?) identity

Real Analysis
Post Reply
akotronis
Former Team Member
Former Team Member
Posts: 36
Joined: Mon Nov 09, 2015 12:29 am

A (combinatorial..?) identity

#1

Post by akotronis »

Show that \(\displaystyle\sum_{k=0}^{n-1}(-1)^{n-k-1}\dfrac{(n+k)!}{(k!)^2(n-k-1)!}=n^2\).
Demetres
Former Team Member
Former Team Member
Posts: 77
Joined: Mon Nov 09, 2015 11:52 am
Location: Limassol/Pyla Cyprus
Contact:

Re: A (combinatorial..?) identity

#2

Post by Demetres »

I can prove the identity but I cannot see a combinatorial interpretation.

To prove the identity writing \(a_n\) for the left hand side it is enough to show that \[ A(x) := \sum_{n=0}^{\infty} a_nx^n = \sum_{n=0}^{\infty} n^2 x^n.\] Since \[ \sum_{n=0}x^n = \frac{1}{1-x}\] then \[ \sum_{n=0}nx^{n-1} = \frac{1}{(1-x)^2}\] and \[ \sum_{n=0}n(n-1)x^{n-2} = \frac{2}{(1-x)^3}\] so \[ \sum_{n=0}^{\infty} n^2 x^n = \frac{2x^2}{(1-x)^3} + \frac{x(1+x)}{(1-x)^2}. \] Here all sums converges absolutely for \(|x| < 1\) and so in this range we are entitled to differentiate term by term e.t.c.

To calculate \(A(x)\) we interchange the order of summation to get \[ A(x) = \sum_{k=0}^{\infty} \frac{(2k+1)!}{k!k!} \sum_{n=k+1}^{\infty} (-1)^{n-k-1} \binom{n+k}{n-k-1}x^n = \sum_{k=0}^{\infty} \frac{(2k+1)!}{k!k!} x^{k+1}\sum_{m=0}^{\infty} \binom{m+2k+1}{m} (-x)^m.\] The "inside" summation is a standard one (see e.g. (2.5.7) in the second edition of the generatingfunctionology book by Wilf) and gives \[ \frac{1}{(1+x)^{2k+2}}.\] So \[ A(x) = \sum_{k=0}^{\infty} (2k+1) \binom{2k}{k} \left( \frac{x}{(1+x)^2}\right)^{k+1}.\] To compute this, we use that \[ \sum_{k=0}^{\infty} \binom{2k}{k} z^{2k+1} = \frac{z}{\sqrt{1-4z^2}}\] (see e.g. (2.5.11) in the same book). Differentiating we get \[ \sum_{k=0}^{\infty} (2k+1)\binom{2k}{k}z^{2k} = \frac{1}{(1-4z^2)^{3/2}}.\] This gives \[ A(x) = \frac{x}{(1+x)^2} \frac{1}{\left(1 - \frac{4x}{(1+x)^2} \right)^{3/2}} = \frac{x}{(1+x)^2} \frac{(1+x)^3}{(1-x)^3} = \frac{x(1+x)}{(1-x)^3}.\] This completes the non-combinatorial proof. I will be interested to see a combinatorial proof if it is known.
akotronis
Former Team Member
Former Team Member
Posts: 36
Joined: Mon Nov 09, 2015 12:29 am

Re: A (combinatorial..?) identity

#3

Post by akotronis »

Thank you for your solution Demetres. I don't have a combinatorial proof either. Here is the solution I had given for this one on http://www.mathematica.gr.:

At first we have

\(\begin{aligned}\displaystyle\sum_{k=0}^{n-1}(-1)^{n-k-1}\dfrac{(n+k)!}{(k!)^2(n-k-1)!}&=\sum_{k=0}^{n-1}(-1)^{n-k-1}(n-k)\binom{n+k}{2k}\binom{2k}{k}\notag \\ &=\sum_{k\geq0}(-1)^{n-k-1}(n-k)\binom{n+k}{2k}\binom{2k}{k}\notag \\ :&=nA_n-B_n.\end{aligned}\)

since the sum equals zero for \(n\geq k\).

We use that

\[\displaystyle \sum_{k\geq0}(-1)^{k-1}\binom{2k}{k}z^k=(4z+1)^{-1/2},\qquad |z|<1/4\hspace{10ex}(1)\] and

\[\displaystyle\sum_{k\geq0}(-1)^{k-1}\binom{2k}{k}z^k=2z(4z+1)^{-3/2},\qquad |z|<1/4\hspace{10ex}(2).\]

Now, for an appropriate circle \(R\) centered at the origin so that we have \(\displaystyle{\left|\frac{z+1}{z^2}\right|<\rho}\) for some \(\rho<1/4\), (and hence uniform convergence on \((1)\) and \((2)\) for \(\displaystyle{\frac{z+1}{z^2}}\) in place of \(z\)), we get

\(\begin{aligned}A_n&=\sum_{k\geq0}(-1)^{n-k-1}\int_R\frac{(z+1)^{n+k}}{z^{2k}}\binom{2k}{k}\stackrel{*}{=}(-1)^n\int_R\frac{(z+1)^n}{z}\sum_{k\geq0}(-1)^{k+1}\left(\frac{z+1}{z^2}\right)\binom{2k}{k}\\&\stackrel{(1)}{=}(-1)^{n+1}\int_R\frac{(z+1)^n}{z+2}.\notag\end{aligned}\)

Now since \(\displaystyle{\frac{(z+1)^n}{z+2}}\) has a pole of first order on \(-2\), from the residue theorem the laast integral equals \[\displaystyle{\lim_{z\to-2}\frac{1}{(1-1)!}\frac{d^{1-1}}{dz^{1-1}}\left((z+2)\frac{(z+1)^n}{z+2}\right)=(-1)^n},\] hence \[\displaystyle{A_n=-1}.\]

(*) The change of summation-integration order is justified by the uniform convergence.

Similarly, and using \((2)\) this time, we get that \(B_n=n(n+1)\), which gives us what we wanted.

Edit: (And I lost a minus sign somewhere...:()
Post Reply

Create an account or sign in to join the discussion

You need to be a member in order to post a reply

Create an account

Not a member? register to join our community
Members can start their own topics & subscribe to topics
It’s free and only takes a minute

Register

Sign in

Who is online

Users browsing this forum: No registered users and 8 guests