 |
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:
$$\begin{multline*} f(b,c,n)=\sum_{a=0}^n \binom{2a+c}{a}\binom{b-c-2a-1}{n-a}+\sum_{a=0}^{n-1} \binom{2a+c}{a}\binom{b-c-2a-1}{n-a-1}=\\ =f(b-1,c,n)+f(b-1,c,n-1). \end{multline*}$$Majd a jobb oldalon:
$$\begin{multline*} f(b,c+1,n)=\sum_{a=0}^n \binom{2a+c}{a}\binom{b-c-2a-1}{n-a}+\sum_{a=0}^n \binom{2a+c}{a-1}\binom{b-c-2a-1}{n-a}=\\ =f(b-1,c,n)+f(b-1,c+2,n-1). \end{multline*}$$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