任意の数 s を k-bonacci数の同じ数を使わずに、和で表現できることの証明

http://codeforces.com/contest/225/problem/B
この問題をgreedyでとける証明

k-bonacci数列とは

$A_0 = 0, A_1 = 1, A_{n} = \sum^{n-1}_{i = max(0,n-k)}A_i$

となる数列のことです。

たとえば k = 2の時、 $\{A_n\} = \{0,1,1,2,3,5,8,13,21\}$ となります(fibnacci数列)

[1]
まず、i = 2..k+1 において、 $A_i = 2^{i-2}$
これは数学的帰納法で証明可能
よって、 $S <= 2^{k}$ となる数Sは、 $A_i (i <= k+1)$ の和を用いて Sを表すことができる

[2]
次に、 $S > 2^{k}$ の時
$A_{m+1} > S >= A_{m}$ なるmを一意に選択できる。
$S' = S - A_m$ と置くと
$2 * A_n > A_{n+1} > A_n (A_n != 1)$ が成り立つことより(帰納法で証明可)
$2 * A_m - A_m > A_{m+1} - A_m > S' > 0$
つまり、 $A_m > S'$ となる

ここで、 $A_{m'+1} > S' >= A_{m'}$ なる m'を一意に選択可能で
かつ m' < m である (∵ m >= m'+1)

この時、 S' <= 2^kなら[1]、そうでなければ[2]に当てはめることができるため
greedyで可能