Dgdrxrt

Can the Produce Flame cantrip be used to grapple, or as an unarmed strike, in the right circumstances?

How would photo IDs work for shapeshifters?

Copycat chess is back

Patience, young "Padovan"

Does it makes sense to buy a new cycle to learn riding?

What is the meaning of "of trouble" in the following sentence?

Is there a familial term for apples and pears?

Could a US political party gain complete control over the government by removing checks & balances?

Why was the "bread communication" in the arena of Catching Fire left out in the movie?

A poker game description that does not feel gimmicky

COUNT(*) or MAX(id) - which is faster?

Why do we use polarized capacitors?

Does a dangling wire really electrocute me if I'm standing in water?

How can I add custom success page

Is this food a bread or a loaf?

Lied on resume at previous job

Can I find out the caloric content of bread by dehydrating it?

How could a lack of term limits lead to a "dictatorship?"

Are objects structures and/or vice versa?

Is there a way to make member function NOT callable from constructor?

How do I create uniquely male characters?

Can a planet have a different gravitational pull depending on its location in orbit around its sun?

What is it called when one voice type sings a 'solo'?

Why did the Germans forbid the possession of pet pigeons in Rostov-on-Don in 1941?

Prove $sum_k2kchoose k^22left(n-kright)choose n-k^2=sum_k(-1)^k16^kn-k choose k2left(n-kright)choose n-k^3$

Show there’s at most $nchoose left lfloorfracn2 rightrfloor$ subsets $Asubset[n]$ such that $displaystylesumlimits_iinA a_i=alpha$Proof that $left(sum^n_k=1x_kright)left(sum^n_k=1y_kright)geq n^2$Combinatorics proof of “sum of (k choose m) with k from m up to n is equal to n+1 choose m+1”Showing $n + a - 1 choose a - 1 = sum_k = 0^leftlfloor n/2 rightrfloor a choose n-2kk+a-1 choose a-1$A comprehensive problem about $sum fracncosh left( nx right)sinh left( npi right) $Showing that $ leftlfloor fracn-12rightrfloor +leftlfloor fracn+24rightrfloor + leftlfloorfracn+44 rightrfloor =n$How to evaluate this sum $sumlimits_i=1^n left lfloor sqrt2 cdot i right rfloor$Prove $2nchoose0 + 2nchoose2 + dots + 2nchoose2n = 2^2n-1$How many $m$ such that : $sumlimits_k=1^m leftlfloorfracmkrightrfloor$ be even?Double sum over $leftlfloorac+bdover krightrfloor$

7

4

$begingroup$

So I've come across this one :

$$forall ninmathbbN,sumlimits_k=0^nleft[2kchoose k2left(n-kright)choose n-kright]^2=sumlimits_k=0^leftlfloorfracn2rightrfloorleft(-1right)^k16^kn-k choose k2left(n-kright)choose n-k^3$$
It looks nice, but since I am not really familiar with combinatorics, I have no clue as how to prove it.

What would you suggest ?

calculus combinatorics summation

share|cite|improve this question

edited Mar 30 at 3:30

Mike Earnest

27.3k22152

asked Mar 17 at 16:22

Harmonic SunHarmonic Sun

71710

$endgroup$

add a comment | 

7

4

$begingroup$

So I've come across this one :

$$forall ninmathbbN,sumlimits_k=0^nleft[2kchoose k2left(n-kright)choose n-kright]^2=sumlimits_k=0^leftlfloorfracn2rightrfloorleft(-1right)^k16^kn-k choose k2left(n-kright)choose n-k^3$$
It looks nice, but since I am not really familiar with combinatorics, I have no clue as how to prove it.

What would you suggest ?

calculus combinatorics summation

share|cite|improve this question

edited Mar 30 at 3:30

Mike Earnest

27.3k22152

asked Mar 17 at 16:22

Harmonic SunHarmonic Sun

71710

$endgroup$

add a comment | 

$begingroup$

So I've come across this one :

$$forall ninmathbbN,sumlimits_k=0^nleft[2kchoose k2left(n-kright)choose n-kright]^2=sumlimits_k=0^leftlfloorfracn2rightrfloorleft(-1right)^k16^kn-k choose k2left(n-kright)choose n-k^3$$
It looks nice, but since I am not really familiar with combinatorics, I have no clue as how to prove it.

What would you suggest ?

calculus combinatorics summation

share|cite|improve this question

edited Mar 30 at 3:30

Mike Earnest

27.3k22152

asked Mar 17 at 16:22

Harmonic SunHarmonic Sun

71710

$endgroup$

share|cite|improve this question

edited Mar 30 at 3:30

Mike Earnest

27.3k22152

asked Mar 17 at 16:22

Harmonic SunHarmonic Sun

71710

share|cite|improve this question

edited Mar 30 at 3:30

Mike Earnest

27.3k22152

asked Mar 17 at 16:22

Harmonic SunHarmonic Sun

71710

edited Mar 30 at 3:30

Mike Earnest

27.3k22152

edited Mar 30 at 3:30

Mike Earnest

27.3k22152

asked Mar 17 at 16:22

Harmonic SunHarmonic Sun

71710

asked Mar 17 at 16:22

Harmonic SunHarmonic Sun

71710

1 Answer
1

active

oldest

votes

3

$begingroup$

Not an answer but too long for a comment. The Maple sumtools
package features an implementation of Zeilberger's algorithm, exported
through the sumrecursion command. This will produce the same
recurrence for the LHS and the RHS. Then we just need to check the two
initial values. This is the Maple transcript.

> with(sumtools);
[Hypersum, Sumtohyper, extended_gosper, gosper, hyperrecursion, hypersum,

 hyperterm, simpcomb, sumrecursion, sumtohyper]

> sumrecursion(binomial(2*k,k)^2*binomial(2*n-2*k,n-k)^2, k,S(n));
 3 2 3
 256 (n - 1) S(-2 + n) - 8 (2 n - 1) (2 n - 2 n + 1) S(n - 1) + S(n) n

> sumrecursion((-1)^k*16^k*binomial(n-k,k)*binomial(2*n-2*k,n-k)^3, k, S(n));
 3 2 3
 256 (n - 1) S(-2 + n) - 8 (2 n - 1) (2 n - 2 n + 1) S(n - 1) + S(n) n

> A := n -> add(binomial(2*k,k)^2*binomial(2*n-2*k,n-k)^2, k=0..n);
 2 2
 A := n -> add(binomial(2 k, k) binomial(2 n - 2 k, n - k) , k = 0 .. n)

> seq(A(n), n=1..5);
 8, 88, 1088, 14296, 195008

> B := n -> add((-1)^k*16^k*binomial(n-k,k)*binomial(2*n-2*k,n-k)^3, k=0..n);
B := n ->

 k k 3
 add((-1) 16 binomial(n - k, k) binomial(2 n - 2 k, n - k) , k = 0 .. n)

> seq(B(n), n=1..5);
 8, 88, 1088, 14296, 195008

The common recurrence is

$$256, left( n-1 right) ^3S left( n-2 right) -8, left( 2,n-1
right) left( 2,n^2-2,n+1 right) S left( n-1 right) +S
left( n right) n^3 = 0.$$

This is a classic example from the foreword to the book A=B by
Petkovsek, Wilf, and Zeilberger, and identified as such at OEIS
A036917.

share|cite|improve this answer

edited Mar 20 at 18:30

answered Mar 20 at 18:20

Marko RiedelMarko Riedel

41.3k340111

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I think this is an answer! It gives an inductive proof of the equation.
  $endgroup$
  – Mike Earnest
  Mar 20 at 18:53
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @MikeEarnest Should not the recurrence formula be proven in an uderstandable way?
  $endgroup$
  – user
  Mar 20 at 23:35
  
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3151733%2fprove-sum-k2k-choose-k22-leftn-k-right-choose-n-k2-sum-k-1k16kn%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

3

$begingroup$

Not an answer but too long for a comment. The Maple sumtools
package features an implementation of Zeilberger's algorithm, exported
through the sumrecursion command. This will produce the same
recurrence for the LHS and the RHS. Then we just need to check the two
initial values. This is the Maple transcript.

> with(sumtools);
[Hypersum, Sumtohyper, extended_gosper, gosper, hyperrecursion, hypersum,

 hyperterm, simpcomb, sumrecursion, sumtohyper]

> sumrecursion(binomial(2*k,k)^2*binomial(2*n-2*k,n-k)^2, k,S(n));
 3 2 3
 256 (n - 1) S(-2 + n) - 8 (2 n - 1) (2 n - 2 n + 1) S(n - 1) + S(n) n

> sumrecursion((-1)^k*16^k*binomial(n-k,k)*binomial(2*n-2*k,n-k)^3, k, S(n));
 3 2 3
 256 (n - 1) S(-2 + n) - 8 (2 n - 1) (2 n - 2 n + 1) S(n - 1) + S(n) n

> A := n -> add(binomial(2*k,k)^2*binomial(2*n-2*k,n-k)^2, k=0..n);
 2 2
 A := n -> add(binomial(2 k, k) binomial(2 n - 2 k, n - k) , k = 0 .. n)

> seq(A(n), n=1..5);
 8, 88, 1088, 14296, 195008

> B := n -> add((-1)^k*16^k*binomial(n-k,k)*binomial(2*n-2*k,n-k)^3, k=0..n);
B := n ->

 k k 3
 add((-1) 16 binomial(n - k, k) binomial(2 n - 2 k, n - k) , k = 0 .. n)

> seq(B(n), n=1..5);
 8, 88, 1088, 14296, 195008

The common recurrence is

$$256, left( n-1 right) ^3S left( n-2 right) -8, left( 2,n-1
right) left( 2,n^2-2,n+1 right) S left( n-1 right) +S
left( n right) n^3 = 0.$$

This is a classic example from the foreword to the book A=B by
Petkovsek, Wilf, and Zeilberger, and identified as such at OEIS
A036917.

share|cite|improve this answer

edited Mar 20 at 18:30

answered Mar 20 at 18:20

Marko RiedelMarko Riedel

41.3k340111

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I think this is an answer! It gives an inductive proof of the equation.
  $endgroup$
  – Mike Earnest
  Mar 20 at 18:53
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @MikeEarnest Should not the recurrence formula be proven in an uderstandable way?
  $endgroup$
  – user
  Mar 20 at 23:35
  
  

  
  
  
  

add a comment | 

3

$begingroup$

Not an answer but too long for a comment. The Maple sumtools
package features an implementation of Zeilberger's algorithm, exported
through the sumrecursion command. This will produce the same
recurrence for the LHS and the RHS. Then we just need to check the two
initial values. This is the Maple transcript.

> with(sumtools);
[Hypersum, Sumtohyper, extended_gosper, gosper, hyperrecursion, hypersum,

 hyperterm, simpcomb, sumrecursion, sumtohyper]

> sumrecursion(binomial(2*k,k)^2*binomial(2*n-2*k,n-k)^2, k,S(n));
 3 2 3
 256 (n - 1) S(-2 + n) - 8 (2 n - 1) (2 n - 2 n + 1) S(n - 1) + S(n) n

> sumrecursion((-1)^k*16^k*binomial(n-k,k)*binomial(2*n-2*k,n-k)^3, k, S(n));
 3 2 3
 256 (n - 1) S(-2 + n) - 8 (2 n - 1) (2 n - 2 n + 1) S(n - 1) + S(n) n

> A := n -> add(binomial(2*k,k)^2*binomial(2*n-2*k,n-k)^2, k=0..n);
 2 2
 A := n -> add(binomial(2 k, k) binomial(2 n - 2 k, n - k) , k = 0 .. n)

> seq(A(n), n=1..5);
 8, 88, 1088, 14296, 195008

> B := n -> add((-1)^k*16^k*binomial(n-k,k)*binomial(2*n-2*k,n-k)^3, k=0..n);
B := n ->

 k k 3
 add((-1) 16 binomial(n - k, k) binomial(2 n - 2 k, n - k) , k = 0 .. n)

> seq(B(n), n=1..5);
 8, 88, 1088, 14296, 195008

The common recurrence is

$$256, left( n-1 right) ^3S left( n-2 right) -8, left( 2,n-1
right) left( 2,n^2-2,n+1 right) S left( n-1 right) +S
left( n right) n^3 = 0.$$

This is a classic example from the foreword to the book A=B by
Petkovsek, Wilf, and Zeilberger, and identified as such at OEIS
A036917.

share|cite|improve this answer

edited Mar 20 at 18:30

answered Mar 20 at 18:20

Marko RiedelMarko Riedel

41.3k340111

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I think this is an answer! It gives an inductive proof of the equation.
  $endgroup$
  – Mike Earnest
  Mar 20 at 18:53
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @MikeEarnest Should not the recurrence formula be proven in an uderstandable way?
  $endgroup$
  – user
  Mar 20 at 23:35
  
  

  
  
  
  

add a comment | 

$begingroup$

Not an answer but too long for a comment. The Maple sumtools
package features an implementation of Zeilberger's algorithm, exported
through the sumrecursion command. This will produce the same
recurrence for the LHS and the RHS. Then we just need to check the two
initial values. This is the Maple transcript.

> with(sumtools);
[Hypersum, Sumtohyper, extended_gosper, gosper, hyperrecursion, hypersum,

 hyperterm, simpcomb, sumrecursion, sumtohyper]

> sumrecursion(binomial(2*k,k)^2*binomial(2*n-2*k,n-k)^2, k,S(n));
 3 2 3
 256 (n - 1) S(-2 + n) - 8 (2 n - 1) (2 n - 2 n + 1) S(n - 1) + S(n) n

> sumrecursion((-1)^k*16^k*binomial(n-k,k)*binomial(2*n-2*k,n-k)^3, k, S(n));
 3 2 3
 256 (n - 1) S(-2 + n) - 8 (2 n - 1) (2 n - 2 n + 1) S(n - 1) + S(n) n

> A := n -> add(binomial(2*k,k)^2*binomial(2*n-2*k,n-k)^2, k=0..n);
 2 2
 A := n -> add(binomial(2 k, k) binomial(2 n - 2 k, n - k) , k = 0 .. n)

> seq(A(n), n=1..5);
 8, 88, 1088, 14296, 195008

> B := n -> add((-1)^k*16^k*binomial(n-k,k)*binomial(2*n-2*k,n-k)^3, k=0..n);
B := n ->

 k k 3
 add((-1) 16 binomial(n - k, k) binomial(2 n - 2 k, n - k) , k = 0 .. n)

> seq(B(n), n=1..5);
 8, 88, 1088, 14296, 195008

The common recurrence is

$$256, left( n-1 right) ^3S left( n-2 right) -8, left( 2,n-1
right) left( 2,n^2-2,n+1 right) S left( n-1 right) +S
left( n right) n^3 = 0.$$

This is a classic example from the foreword to the book A=B by
Petkovsek, Wilf, and Zeilberger, and identified as such at OEIS
A036917.

share|cite|improve this answer

edited Mar 20 at 18:30

answered Mar 20 at 18:20

Marko RiedelMarko Riedel

41.3k340111

$endgroup$

> with(sumtools);
[Hypersum, Sumtohyper, extended_gosper, gosper, hyperrecursion, hypersum,

 hyperterm, simpcomb, sumrecursion, sumtohyper]

> sumrecursion(binomial(2*k,k)^2*binomial(2*n-2*k,n-k)^2, k,S(n));
 3 2 3
 256 (n - 1) S(-2 + n) - 8 (2 n - 1) (2 n - 2 n + 1) S(n - 1) + S(n) n

> sumrecursion((-1)^k*16^k*binomial(n-k,k)*binomial(2*n-2*k,n-k)^3, k, S(n));
 3 2 3
 256 (n - 1) S(-2 + n) - 8 (2 n - 1) (2 n - 2 n + 1) S(n - 1) + S(n) n

> A := n -> add(binomial(2*k,k)^2*binomial(2*n-2*k,n-k)^2, k=0..n);
 2 2
 A := n -> add(binomial(2 k, k) binomial(2 n - 2 k, n - k) , k = 0 .. n)

> seq(A(n), n=1..5);
 8, 88, 1088, 14296, 195008

> B := n -> add((-1)^k*16^k*binomial(n-k,k)*binomial(2*n-2*k,n-k)^3, k=0..n);
B := n ->

 k k 3
 add((-1) 16 binomial(n - k, k) binomial(2 n - 2 k, n - k) , k = 0 .. n)

> seq(B(n), n=1..5);
 8, 88, 1088, 14296, 195008

share|cite|improve this answer

edited Mar 20 at 18:30

answered Mar 20 at 18:20

Marko RiedelMarko Riedel

41.3k340111

answered Mar 20 at 18:20

Marko RiedelMarko Riedel

41.3k340111

answered Mar 20 at 18:20

Marko RiedelMarko Riedel

41.3k340111