, 2014

With $m = n + k + 1$ and $j = k + 1 - i$, we obtain for $n \ge 1$
$$f_k(n + k + 1) = \sum_{i=0}^{k} \binom{k+1}{i} f_k(n + i).$$
This shows that $a_i = \binom{k+1}{i}$ are the integers that solve the problem.

Define $r = \sqrt[k+1]{2}$, so that $r^{k+1} = 2$ and let
$$F = 1 + r + r^2 + \dots + r^k = \frac{r^{k+1} - 1}{r-1} = \frac{1}{r-1}.$$
Also define $F_n = \sum_{j=0}^{k} f_{k-j}(n)r^j$ for integers $n \ge 1$, then $F_1 = F$.
First we would like to show that $F \cdot F_n = F_{n+1}$ for all $n \ge 1$. As $F = \frac{1}{r-1}$, this is equivalent to showing that $rF_{n+1} = F_n + F_{n+1}$.
To prove this, we will use the identity $f_k(n+1) + f_k(n) = 2f_0(n+1)$, which is obtained as follows. First observe that the defining recursion for the $f_j$ implies
$$f_j(n+1) = 2 \sum_{i=0}^{k} f_i(n) - \sum_{i=j}^{k} f_i(n)$$
for all $j \ge 0$ and $n \ge 1$. In particular, for $j = k$, we obtain
$$f_k(n+1) = 2 \sum_{i=0}^{k} f_i(n) - f_k(n) = 2f_0(n+1) - f_k(n),$$
as required. Using this identity, we obtain now
$$\begin{align*} F_n + F_{n+1} &= \sum_{j=0}^{k} (f_{k-j}(n) + f_{k-j}(n+1))r^j \\ &= (f_k(n) + f_k(n+1)) + \sum_{j=1}^{k} f_{k-j+1}(n+1)r^j \\ &= 2f_0(n+1) + \sum_{j=0}^{k-1} f_{k-j}(n+1)r^{j+1} \\ &= \sum_{j=0}^{k} f_{k-j}(n+1)r^{j+1} = rF_{n+1}. \end{align*}$$
This proves that $F \cdot F_n = F_{n+1}$, from which we obtain $F_n = F^n$ for all $n \ge 1$.
From $F = \frac{1}{r-1}$ we get $r = \frac{F+1}{F}$ and so $2 = r^{k+1} = \left(\frac{F+1}{F}\right)^{k+1}$. This gives $2F^{k+1} = (F+1)^{k+1}$ and we obtain
$$F^{k+1} = \sum_{i=0}^{k} \binom{k+1}{i} F^i \quad \text{and so} \quad F^{n+k+1} = \sum_{i=0}^{k} \binom{k+1}{i} F^{n+i}.$$
Because $F^n = F_n$ this can be rewritten as
$$F_{n+k+1} = \sum_{i=0}^{k} \binom{k+1}{i} F_{n+i} \quad \text{that is}$$
$$\sum_{j=0}^{k} f_{k-j}(n+k+1)r^j = \sum_{j=0}^{k} \sum_{i=0}^{k} \binom{k+1}{i} f_{k-j}(n+i)r^j.$$
Because the only rational numbers $t_0, \dots, t_k$ satisfying $t_0 + t_1 r + \dots + t_k r^k = 0$ are $t_0 = t_1 = \dots = t_k = 0$ (see Problem 19), by comparing the terms with $j = 0$, we obtain
$$f_k(n + k + 1) = \sum_{i=0}^{k} \binom{k+1}{i} f_k(n + i).$$
This shows that $a_i = \binom{k+1}{i}$ are the integers that solve the problem.