A (combinatorial..?) identity
A (combinatorial..?) identity
Show that \(\displaystyle\sum_{k=0}^{n-1}(-1)^{n-k-1}\dfrac{(n+k)!}{(k!)^2(n-k-1)!}=n^2\).
-
- Former Team Member
- Posts: 77
- Joined: Mon Nov 09, 2015 11:52 am
- Location: Limassol/Pyla Cyprus
- Contact:
Re: A (combinatorial..?) identity
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.
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.
Re: A (combinatorial..?) identity
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...)
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...)
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
Sign in
Who is online
Users browsing this forum: No registered users and 8 guests