hard binomial sum

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

hard binomial sum

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

PRMOisTheHardestExam

409 posts

PRMOisTheHardestExam

#1 h Mar 6, 2023, 5:35 PM

Y by

Find
$\frac{\displaystyle\sum_{k=0}^r \binom nk \binom{n-2k}{r-k}}{\displaystyle\sum_{k=r}^n \binom nk \binom{2k}{2r}\left(\frac{3}{4}\right)^{n-k}\left(\frac{1}{2}\right)^{2k-2r}}$ \
where $n \ge 2r$ .
Options: 1/2, 1, 2, none.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

PRMOisTheHardestExam

409 posts

PRMOisTheHardestExam

#2 h Mar 30, 2023, 6:18 PM

Y by

bump

//////

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

351 posts

#3 h Mar 30, 2023, 6:41 PM • 1 Y

Y by honey_lemon

1 is the answer as both are the expansions of $(x^2+x+1)^n$ in different forms i suppose

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

218 posts

#4 h Mar 31, 2023, 3:46 AM

Y by

@inbox please explain How you guess $(x^2+x+1)^n$ and how you get $1$

This post has been edited 1 time. Last edited by girishpimoli, Mar 31, 2023, 3:47 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

218 posts

#5 h Apr 30, 2023, 3:55 PM

Y by

PRMOisTheHardestExam wrote:

Find
$\frac{\displaystyle\sum_{k=0}^r \binom nk \binom{n-2k}{r-k}}{\displaystyle\sum_{k=r}^n \binom nk \binom{2k}{2r}\left(\frac{3}{4}\right)^{n-k}\left(\frac{1}{2}\right)^{2k-2r}}$ \
where $n \ge 2r$ .
Options: 1/2, 1, 2, none.

Please look on that problem

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

226 posts

#6 h Jan 21, 2025, 4:47 PM

Y by

I guess there's a slight correction in the numerator
It should be $\binom{n}{2i}$ instead of $\binom{n}{i}$
Then the correct answer is $1.$

This post has been edited 1 time. Last edited by P162008, Apr 24, 2025, 1:16 AM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

RITESH_ZANJURNE

5 posts

RITESH_ZANJURNE

#7 h Jan 21, 2025, 5:00 PM

Y by

P162008 wrote:

I guess there's a slight correction in the numerator
It should be C(n,2k) instead of C(n,k).
Then the correct answer is 1.

Soln sir?

This post has been edited 1 time. Last edited by RITESH_ZANJURNE, Jan 21, 2025, 5:00 PM
Reason: .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

226 posts

#8 h Apr 24, 2025, 1:15 AM

Y by

P162008 wrote:

I guess there's a typo in the numerator
It should be $\binom{n}{2i}$ instead of $\binom{n}{i}$
Then the correct answer is $1$

Let $\zeta = \sum_{i=0}^{r} \binom{n}{2i}\binom{n-2i}{r-i}$

Now, define a generating function $\alpha(x)$ as $\alpha(x) = \sum_{r=0}^{\infty} \zeta x^r = \sum_{r=0}^{\infty} \sum_{i=0}^{r} \binom{n}{2i} \binom{n-2i}{r-i} x^r$

On swapping the order of summation, we get

$\alpha(x) = \sum_{i=0}^{\infty} \sum_{r=i}^{\infty} \binom{n}{2i} \binom{n-2i}{r-i} x^r = \sum_{i=0}^{\infty} \binom{n}{2i} x^i \sum_{r=i}^{\infty} \binom{n-2i}{r-i} x^{r-i}$

Let $r - i = t$ then $0 \leqslant r - i < \infty$ as $i \leqslant r < \infty$

Now, $\alpha(x) = \sum_{i=0}^{\infty} \binom{n}{2i} x^i \sum_{t=0}^{\infty} \binom{n-2i}{t} x^t = \sum_{i=0}^{\infty} \binom{n}{2i} x^i (1 + x)^{n - 2i} = (1 + x)^n \sum_{i=0}^{\infty} \binom{n}{2i} \left(\frac{\sqrt{x}}{1 + x}\right)^{2i}$

Then, $\alpha(x) = (1 + x)^n \left[\frac{(1 + \frac{\sqrt{x}}{1 + x})^n + (1 - \frac{\sqrt{x}}{1 + x})^n}{2}\right] = \frac{1}{2} \left[(1 + \sqrt{x} + x)^n + (1 - \sqrt{x} + x)^n\right]$

$\boxed{\therefore \zeta = \left[x^r\right] \frac{1}{2} \left[(1 + \sqrt{x} + x)^n + (1 - \sqrt{x} + x)^n\right]}$

Similarly, Let $\xi = \sum_{i=r}^{n} \binom{n}{i} \binom{2i}{2r} \left(\frac{1}{2}\right)^{2i - 2r} \left(\frac{3}{4}\right)^{n- i}$

Again, define a generating function $\beta(x)$ as $\beta(x) = \sum_{r=0}^{\infty} \xi x^r = \sum_{r=0}^{\infty} \sum_{i=r}^{n} \binom{n}{i} \binom{2i}{2r} \left(\frac{1}{2}\right)^{2i-2r} \left(\frac{3}{4}\right)^{n- i} x^r$

On swapping the order of summation, we get

$\beta(x) = \sum_{i=0}^{\infty} \sum_{r=0}^{i} \binom{n}{i} \binom{2i}{2r} \left(\frac{1}{2}\right)^{2i-2r} \left(\frac{3}{4}\right)^{n- i} x^r = \sum_{i=0}^{\infty} \binom{n}{i} \left(\frac{3}{4}\right)^{n - i} \left(\frac{1}{4}\right)^i \sum_{r=0}^{i} \binom{2i}{2r} \left(2\sqrt{x}\right)^{2r}$

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

Then, $\beta(x) = \frac{1}{2} \left[\sum_{i=0}^{\infty} \binom{n}{i} \left(\frac{3}{4}\right)^{n-i} \left(x + \sqrt{x} + \frac{1}{4}\right)^i + \sum_{i=0}^{\infty} \binom{n}{i} \left(\frac{3}{4}\right)^{n-i} \left(x - \sqrt{x} + \frac{1}{4}\right)^i \right] = \frac{1}{2} \left[(1 + \sqrt{x} + x)^n + (1 - \sqrt{x} + x)^n\right]$

$\boxed{\therefore \xi = \left[x^r\right] \frac{1}{2} \left[(1 + \sqrt{x} + x)^n + (1 - \sqrt{x} + x)^n\right]}$

Finally, $\boxed{\left(\frac{\zeta}{\xi}\right) = 1}$

This post has been edited 2 times. Last edited by P162008, Apr 24, 2025, 1:18 AM
Reason: Typo

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a