Problem B. 5348. (November 2023)
B. 5348. Let \(\displaystyle b\), \(\displaystyle c\) and \(\displaystyle n\) be non-negative integers satisfying \(\displaystyle 0\le c\le b-2n\). Prove that
\(\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}. \)
Proposed by L. Tóthmérész, Budapest
(6 pont)
Deadline expired on December 11, 2023.
Sorry, the solution is available only in Hungarian. Google translation
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.
Statistics:
21 students sent a solution. 6 points: Bodor Mátyás, Diaconescu Tashi, Gömze Norken, Holló Martin, Jármai Roland, Szakács Ábel. 4 points: 4 students. 3 points: 5 students. 1 point: 1 student. 0 point: 5 students.
Problems in Mathematics of KöMaL, November 2023