A B. 5348. feladat (2023. november)

B. 5348. Legyenek $\displaystyle b$, $\displaystyle c$ és $\displaystyle n$ nemnegatív egészek, melyekre $\displaystyle 0\le c\le b-2n$ teljesül. Mutassuk meg, hogy

$\displaystyle \sum_{a=0}^n \binom{2a}{a}\binom{b-2a}{n-a} = \sum_{a=0}^n \binom{2a+c}{a}\binom{b-c-2a}{n-a}.$

Javasolta: Tóthmérész Lilla (Budapest)

(6 pont)

A beküldési határidő 2023. december 11-én LEJÁRT.

Megoldás. Legyen

$\displaystyle f(b,c,n):=\sum_{a=0}^n \binom{2a+c}{a}\binom{b-c-2a}{n-a},$

ha a $\displaystyle b$, $\displaystyle c$, $\displaystyle n$ nemnegatív egész számokra $\displaystyle 0\leq c\leq b-2n$. A feladat az $\displaystyle f(b,0,n)=f(b,c,n)$ egyenlőség igazolása. Ezt $\displaystyle n$ szerinti teljes indukcióval bizonyítjuk.

Az indukció kezdőlépésénél $\displaystyle n=0$, ekkor

$\displaystyle f(b,0,0)=\binom{0}{0}\binom{b}{0}=1=\binom{c}{0}\binom{b-c}{0}=f(b,c,0)$

valóban teljesül.

Az indukciós lépéshez tegyük most fel, hogy $\displaystyle n\geq 1$ és $\displaystyle (n-1)$-re már igazoltuk az állítást (minden, a feltételeknek eleget tevő $\displaystyle b$, $\displaystyle c$ mellett). Elegendő igazolnunk, hogy $\displaystyle f(b,c,n)=f(b,c+1,n)$, ha $\displaystyle 0\leq c\leq b-2n-1$, hiszen ekkor $\displaystyle f(b,0,n)=f(b,1,n)=\dots=f(b,b-2n,n)$.

Az igazolandó állítás tehát kiírva:

$\displaystyle \sum_{a=0}^n \binom{2a+c}{a}\binom{b-c-2a}{n-a} =\sum_{a=0}^n \binom{2a+c+1}{a}\binom{b-c-2a-1}{n-a} .$

A $\displaystyle \binom{b-c-2a}{n-a}=\binom{b-c-2a-1}{n-a}+\binom{b-c-2a}{n-a-1}$ (itt $\displaystyle a=n$-re a második tag 0-nak veendő) és $\displaystyle \binom{2a+c+1}{a}=\binom{2a+c}{a}+\binom{2a+c}{a-1}$ (itt $\displaystyle a=0$-ra a második tag 0-nak veendő) azonosságokat fogjuk használni, hiszen így mindkét oldalon megjelenik ugyanaz az összeg.

Először a bal oldalon:

Majd a jobb oldalon:

Ezek alapján $\displaystyle f(b,c,n)=f(b,c+1,n)$ pontosan akkor teljesül, ha $\displaystyle f(b-1,c,n-1)=f(b-1,c+2,n-1)$. Ellenőrizzük, hogy alkalmazható-e az indukciós feltevés. Mivel $\displaystyle 1\leq n$, ezért $\displaystyle 1\leq 2n-1\leq b$, így minden érték nemnegatív. Így az szükséges, hogy $\displaystyle 0\leq c\leq c+2\leq (b-1)-2(n-1)$ legyen. Mivel $\displaystyle 0\leq c\leq b-2n-1$, ezért ez teljesül, így az indukciós feltevést használva kapjuk, hogy $\displaystyle f(b,c,n)=f(b,c+1,n)$ is fennáll. Ezzel az indukciós lépést igazoltuk, amivel a feladat állításának bizonyítását befejeztük.

Statisztika:

21 dolgozat érkezett.
6 pontot kapott:	Bodor Mátyás, Diaconescu Tashi, Gömze Norken, Holló Martin, Jármai Roland, Szakács Ábel.
4 pontot kapott:	4 versenyző.
3 pontot kapott:	5 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	5 versenyző.

A KöMaL 2023. novemberi matematika feladatai