Sum

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

Sum

Unread post by yo79 » Mon Feb 04, 2013 1:05 am

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

Unread post by Prosenjit Basak » Tue Feb 05, 2013 9:23 pm

I am sorry but I couldn't understand what you are trying to say? :oops: :oops: Please explain it. :oops:
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

Unread post by yo79 » Wed Feb 06, 2013 2:00 am

To calculate this sum!

User avatar
Phlembac Adib Hasan
Posts: 1012
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

Re: Sum

Unread post by Phlembac Adib Hasan » Wed Feb 06, 2013 9:36 am

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

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

Re: Sum

Unread post by sowmitra » Wed Feb 06, 2013 12:07 pm

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

Unread post by yo79 » Wed Feb 06, 2013 1:25 pm

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

Unread post by sourav das » Wed Feb 06, 2013 5:19 pm

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

Re: Sum

Unread post by yo79 » Thu Feb 07, 2013 2:33 am

Thank you!

Post Reply