## Sum

For discussing Olympiad Level Combinatorics problems
yo79
Posts: 53
Joined: Mon Feb 04, 2013 1:01 am

### Sum

Find a closed formula for:
$\displaystyle \sum\limits_{i,j=0}^\infty\binom{n}{3i}\binom{n-3i}{3j}$

Prosenjit Basak
Posts: 53
Joined: Wed Nov 28, 2012 12:48 pm

### Re: Sum

I am sorry but I couldn't understand what you are trying to say? Please explain it.
Yesterday is past, tomorrow is a mystery but today is a gift.

yo79
Posts: 53
Joined: Mon Feb 04, 2013 1:01 am

### Re: Sum

To calculate this sum!

Posts: 1012
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

### Re: Sum

yo79 wrote:Find a closed formula for:
$\displaystyle \sum\limits_{i,j=0}^\infty\binom{n}{3i}\binom{n-3i}{3j}$
Define $n$ at first. It has been used without any definition. Or do you want a formula for that sum involving $n$?
Welcome to BdMO Online Forum. Check out Forum Guides & Rules: http://forum.matholympiad.org.bd/viewtopic.php?f=25&t=6

sowmitra
Posts: 155
Joined: Tue Mar 20, 2012 12:55 am
Location: Mirpur, Dhaka, Bangladesh

### Re: Sum

I am guessing, $n\in\mathbb{N}$....
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

yo79
Posts: 53
Joined: Mon Feb 04, 2013 1:01 am

### Re: Sum

n is a natural number! The answer must be something simple like: $\binom{n-1}{2n+5}$ or something like $\frac{n^2+n \binom{n}{2n}}{45}$ (these are not the answers but they are some examples of answers) or other form, something like these!

sourav das
Posts: 461
Joined: Wed Dec 15, 2010 10:05 am
Location: Dhaka
Contact:

### Re: Sum

Note that:
$(a+\omega )^n+(a+\omega ^2)^n+(a+1)^n=3\sum_{i=0}^{\infty}\binom{n}{3i}a^{n-3i}$
Where $1+\omega+\omega^2=0$ and $\omega^3=1$

Now,
$\sum_{i=0,j=0}^{\infty}\binom{n}{3i}\binom{n-3i}{3j}=\sum_{i=0}^{\infty}\binom{n}{3i}\left [ \sum_{j=0}^{\infty}\binom{n-3i}{3j}\right ]$

$=\sum_{i=0}^{\infty}\binom{n}{3i}\frac{1}{3}\left [(1+\omega )^{n-3i} +(1+\omega ^2)^{n-3i}+(1+1)^{n-3i}\right ]$

$=\sum_{i=0}^{\infty}\binom{n}{3i}\frac{1}{3}\left [(-\omega )^{n-3i} +(-\omega ^2)^{n-3i}+2^{n-3i}\right ]$

$=\frac{1}{9} [ \left \{ (-\omega ^2+\omega)^n+(-\omega^2+\omega^2)^n+(-\omega^2+1)^n \right \}+$
$\left \{ (-\omega+\omega)^n +(-\omega+\omega^2)^n+(-\omega+1)^n\right \} +$
$\left \{ (2+\omega)^n+(2+\omega^2)^n+(2+1)^n \right \} ]$

$=\frac{1}{9}\left [ (-\omega ^2+\omega )^n+(\omega ^2-\omega )^n+2(-\omega ^2+1)^n+2(-\omega +1)^n+3^n \right ]$

I don't know how to simplify more. I will be grateful to you if you find any other suitable form.
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

yo79
Posts: 53
Joined: Mon Feb 04, 2013 1:01 am

Thank you!