SRM687 div1 250の証明

gistfile1.txt

(命題) 任意の正の整数iについて、2以上A[i+1]未満の全ての数は、A[1], A[2], ..., A[i]の異なる要素の和で表すことができる。

(証明)
数学的帰納法で示す。
(1) i=1,2のとき
  2はA[1]、3はA[2]なので、示せた。
(2) i=k, k+1のときに、命題が成立すると仮定する。
  このとき、i=k+2について、命題(2以上A[k+3]未満の全ての数は、A[1], ..., A[k+2]の異なる要素の和で表すことができる)が成立することを示す。
    (2-i) 2 <= x < A[k+2]のとき
      仮定より、A[1], ..., A[k+1]で表すことができる。
    (2-ii) x = A[k+2]のとき
      A[k+2]で表すことができる
    (2-iii) x = A[k+2]+1のとき
      A[k+2]+1 = A[k+1]+A[k]なので、xはA[k+1]とA[k]の和で表すことができる。
    (2-iv) A[k+2]+2 <= x <= A[k+3]-1のとき
      A[k+3]-1 = A[k+2] + A[k+1]-2 であり、仮定より2以上A[k+1]-2以下の数はA[1], ..., A[k]で表すことができるので、xはA[k+2]とA[1], ..., A[k]のいずれかで表すことができる。
  (2-i)から(2-iv)より、A[k+2]のときも、命題が成立することが示せた。
以上より、命題は示された。