IMO Shortlist 1998 problem A4
Dodao/la:
arhiva2. travnja 2012. For any two nonnegative integers
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
and
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
satisfying
![n\geq k](/media/m/2/2/3/22349f3c42ce62312b2d934d2f62651b.png)
, we define the number
![c(n,k)](/media/m/3/7/0/37048de6a31d483bf72fff0425b50212.png)
as follows:
-
![c\left(n,0\right)=c\left(n,n\right)=1](/media/m/3/e/2/3e295998ee5a0f4fb56ae1706617aace.png)
for all
![n\geq 0](/media/m/7/c/9/7c9155fe4dfe8430a262cb6a8e30f32f.png)
;
-
![c\left(n+1,k\right)=2^{k}c\left(n,k\right)+c\left(n,k-1\right)](/media/m/c/0/7/c071513430ae6d204566fc8797fea735.png)
for
![n\geq k\geq 1](/media/m/9/b/7/9b7c28c1f1773c117cd9369d05c0278f.png)
.
Prove that
![c\left(n,k\right)=c\left(n,n-k\right)](/media/m/a/3/c/a3c52b8e655dce07edb164c070e24ff0.png)
for all
![n\geq k\geq 0](/media/m/d/c/6/dc62440e9c867edbc05f2c612546768a.png)
.
%V0
For any two nonnegative integers $n$ and $k$ satisfying $n\geq k$, we define the number $c(n,k)$ as follows:
- $c\left(n,0\right)=c\left(n,n\right)=1$ for all $n\geq 0$;
- $c\left(n+1,k\right)=2^{k}c\left(n,k\right)+c\left(n,k-1\right)$ for $n\geq k\geq 1$.
Prove that $c\left(n,k\right)=c\left(n,n-k\right)$ for all $n\geq k\geq 0$.
Izvor: Međunarodna matematička olimpijada, shortlist 1998