[math-fun] binomial coefficient puzzle
Prove sum_(j = 0)^(j = n) (2j)_C_j (2n-2j)_C_(n-j) = 4^n eg. with n = 4 , 1.20 + 2.6 + 6.2 + 20.1 = 64 Fred Lunnon
Proof: f(x) := 1/sqrt(1-4*x) = sum_{n=0}^{\infty} \binom{2n}{n} x^n. Your sum is the coefficient of x^n in f(x)^2, i.e. the coefficient of x^n in 1/(1-4*x), which is 4^n. Victor On Wed, Jul 3, 2013 at 11:12 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
Prove sum_(j = 0)^(j = n) (2j)_C_j (2n-2j)_C_(n-j) = 4^n
eg. with n = 4 , 1.20 + 2.6 + 6.2 + 20.1 = 64
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
WFL of course meant "combinatorial proof" :^) * Victor Miller <victorsmiller@gmail.com> [Jul 04. 2013 07:38]:
Proof: f(x) := 1/sqrt(1-4*x) = sum_{n=0}^{\infty} \binom{2n}{n} x^n. Your sum is the coefficient of x^n in f(x)^2, i.e. the coefficient of x^n in 1/(1-4*x), which is 4^n.
Victor
On Wed, Jul 3, 2013 at 11:12 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
Prove sum_(j = 0)^(j = n) (2j)_C_j (2n-2j)_C_(n-j) = 4^n
eg. with n = 4 , 1.20 + 2.6 + 6.2 + 20.1 = 64
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It's true that I do instinctively discount generating functions, despite on one occasion being obliged to employ them to get the best lower bound on the semi-meander / map-folding constant. But Victor's snappy riposte makes me wonder whether the technique can cope with this rather gnarlier convolution, which is actually what I was attempting to prove when I came across that (surely well-known) Pascal triangle identity: B(n+k+1, n-k) = sum_{j = k}^{j = n} B(j+k-1, j-k) B(n-j+1, n-j) where B(n, k) are the ballot numbers / Catalan triangle B(n, k) = {n+k-1}_C_{k} (n-k)/(n+k) = {n+k-1}_C_{k} - {n+k-1}_C_{k-1} --- see OEIS entry A009766 . Note B(n+1, n) = C(n) are Catalan numbers. Fred Lunnon On 7/4/13, Joerg Arndt <arndt@jjj.de> wrote:
WFL of course meant "combinatorial proof" :^)
* Victor Miller <victorsmiller@gmail.com> [Jul 04. 2013 07:38]:
Proof: f(x) := 1/sqrt(1-4*x) = sum_{n=0}^{\infty} \binom{2n}{n} x^n. Your sum is the coefficient of x^n in f(x)^2, i.e. the coefficient of x^n in 1/(1-4*x), which is 4^n.
Victor
On Wed, Jul 3, 2013 at 11:12 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
Prove sum_(j = 0)^(j = n) (2j)_C_j (2n-2j)_C_(n-j) = 4^n
eg. with n = 4 , 1.20 + 2.6 + 6.2 + 20.1 = 64
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It was the elementary ballot number recurrence in disguise all the time: with a change of variables, B(n, k) = sum_j B(n-k-1+j, j) C(k-j) --- how embarrassing! Fred Lunnon On 7/4/13, Fred lunnon <fred.lunnon@gmail.com> wrote:
It's true that I do instinctively discount generating functions, despite on one occasion being obliged to employ them to get the best lower bound on the semi-meander / map-folding constant.
But Victor's snappy riposte makes me wonder whether the technique can cope with this rather gnarlier convolution, which is actually what I was attempting to prove when I came across that (surely well-known) Pascal triangle identity:
B(n+k+1, n-k) = sum_{j = k}^{j = n} B(j+k-1, j-k) B(n-j+1, n-j)
where B(n, k) are the ballot numbers / Catalan triangle
B(n, k) = {n+k-1}_C_{k} (n-k)/(n+k) = {n+k-1}_C_{k} - {n+k-1}_C_{k-1}
--- see OEIS entry A009766 . Note B(n+1, n) = C(n) are Catalan numbers.
Fred Lunnon
On 7/4/13, Joerg Arndt <arndt@jjj.de> wrote:
WFL of course meant "combinatorial proof" :^)
* Victor Miller <victorsmiller@gmail.com> [Jul 04. 2013 07:38]:
Proof: f(x) := 1/sqrt(1-4*x) = sum_{n=0}^{\infty} \binom{2n}{n} x^n. Your sum is the coefficient of x^n in f(x)^2, i.e. the coefficient of x^n in 1/(1-4*x), which is 4^n.
Victor
On Wed, Jul 3, 2013 at 11:12 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
Prove sum_(j = 0)^(j = n) (2j)_C_j (2n-2j)_C_(n-j) = 4^n
eg. with n = 4 , 1.20 + 2.6 + 6.2 + 20.1 = 64
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Fred lunnon -
Joerg Arndt -
Victor Miller