q_n = P(k_1, ... ,k_n) となることを、n に関する帰納法により示す。

p_0 = k_0
q_0 = 1

p_1 = k_0k_1 + 1
q_1 = k_1

だから n = 1 のときは正しい。
n ≧ 1 のとき q_n = P(k_1, ... ,k_n) と仮定する。
q_(n+1) = q_nk_(n+1) + q_(n-1) だから
q_(n+1) = P(k_1, ... ,k_n)k_(n+1) + P(k_1, ... ,k_(n-1))

一方、>>44 より p_n = p_nk_n + p_(n-2)
これは
P(k_0, ... ,k_n)
= P(k_0, ... ,k_(n-1))k_n + P(k_0, ... ,k_(n-2))
を意味する。

この式で k_0, ... ,k_(n-1), k_n を k_1, ... , k_n, k_(n+1) に
置き換えると、
P(k_1, ... ,k_(n+1))
= P(k_1, ... ,k_n)k_(n+1) + P(k_1, ... ,k_(n-1))
よって
q_(n+1) = P(k_1, ... ,k_(n+1))

これで q_n = P(k_1, ... ,k_n) が証明された。