$ f: \mathbb N \times \mathbb Z \rightarrow \mathbb Z$ satisfy the given conditions $ a)$ $ f(0,0)=1$ , $ f(0,1)=1$ , $ b)$ $ \forall k \notin \left\{0,1\right\}$ $ f(0,k)=0$ and $ c)$ $ \forall n \geq 1$ and $ k$ , $ f(n,k)=f(n-1,k)+f(n-1,k-2n)$ find the sum $ \displaystyle\sum_{k=0}^{\binom{2009}{2}}f(2008,k)$
Problem
Source: Turkey NMO 2008 Problem 4
Tags: function, algebra unsolved, algebra
Rust
02.12.2008 08:11
$ f(n,k) = \#\{X|2\sum_i x_i = k \ or k - 1\}$, were $ X$ is subset $ \{1,2,...,n\}$. Therefore $ f(n,n(n + 1) + 1 - k) = f(n,k)$. Let $ F(n,k) = \sum_{i = 0}^k f(n,i)$, then $ F(n,n(n + 1) + 1 - k) + F(n,k) = 2^{n + 1}$. It give $ F(n,\frac {n(n + 1)}{2}) = 2^n.$
ertanrock
07.12.2008 11:15
sinankaral53 wrote: $ f: \mathbb N \times \mathbb Z \rightarrow \mathbb Z$ satisfy the given conditions $ a)$ $ f(0,0) = 1$ , $ f(0,1) = 1$ , $ b)$ $ \forall k \notin \left\{0,1\right\}$ $ f(0,k) = 0$ and $ c)$ $ \forall n \geq 1$ and $ k$ , $ f(n,k) = f(n - 1,k) + f(n - 1,k - 2n)$ find the sum $ \displaystyle\sum_{k = 0}^{\binom{2009}{2}}f(2008,k)$ Turkish solution
Attachments:
soru_4.pdf (65kb)
shohvanilu
18.06.2011 13:37
Lemma1: If $k<0$ or $k<n^2+n+1$ then $f(n,k)=0$ Lemma2: For n,k>0 $f(n,n^2+n+1-k)=f(n,k)$ Lemma3:$ \sum_{k=0}^{\n^2+n+1}f(n,k)=2^n $ Lemma4:$ \sum_{k=0}^{\frac{n^2+n}{2}}f(n,k)=2^n $ $ \sum_{k=0}^{\binom{2009}{2}}f(2008,k)=\sum_{k=0}^{\frac{2008^2+2008}{2}}f(2008,k)=2^{2008} $
euler_brick
18.06.2017 06:18
We create a bijection. Let $ A_m = \{ 1, 2\times 1, ..., 2 \times m \} $ and $ S(X) $ denote the sum of the elements of set $ X$. We claim that $ \boxed{ f(n,m) \text{ counts the number of ways to pick } Q \in A_n \text{ such that } S(Q) = m} $. Call such a set $ Q $ good.
We induct to show this. Base case $ n = 0$ is easy to verify against conditions a) and b).
For $ n = \ell +1 $ notice that $ 2( \ell +1) $ is either in $ Q $ or not, so that helps us split into either $ f(\ell, m) $ in the first and $f(\ell, m - 2(\ell+1))$ for the latter. Combining gives the recursion in c).
So we want to keep the sum of our elements in the bound $ [ 0, \binom{2009}{2} ] $. Remark that $S(A_{2008}) = 2 \binom{2009}{2} + 1 $. As such, if $ Q$ is a good set, then $ A_{2008} \setminus Q $ is not. So we have a bijection between sets that are good and those that are not. Thus, our evaluated sum is just $ \boxed{ \frac{2^{2009}}{2} = 2^{2008}} $.