こうすると証明できそうです。

F_i=a_1+...+a_i (フィボナッチ数列のi項目までの和)
と置きます。このとき、

(1) 1,...,F_iは全部i項目までの部分和で表せる
(2) そのような表し方で足し算の回数が最小となるのはでかい方から貪欲に使った場合である
を帰納法で示します。
i==1のときは明らかです。

j<iである任意のjで(1),(2)が成り立ってると仮定して、iでも成り立つことを示します。

(1)
x <= F_iであるxを表したいとする。 
x < a_i なら、当然 x<=F_{i-1} だから帰納法の仮定が使えてOK
x >= a_iなら、 x <= F_i より、 x-a_i <= F{i-1} となって、x-a_iに帰納法の仮定が使えて、
x = （i-1項目までの部分和） + a_i
と表せるからOK

(2)
x > F_{i-1}だったら当然a_iを使わなきゃいけない。
そうでなくても、a_i <= x であるxを表すときには、絶対a_iを使ったほうがお得であることを示す。
a_i を使わない時、 a_{i-1}まででxを表す事になる。このとき、帰納法の仮定より貪欲に使っていくことになるが、x >= a_i = a_{i-1} + a_{i-2}なので、
x =  a_{i-1} + a_{i-2} + （何か）
という形をしているはずである。どう考えても
x =  a_i + （何か）
とした方がお得である。