問題タブ [induction]

以下は解決策ですが、誘導部分による証明の一部を理解するのに苦労しています。片方に+2、もう片方に+4を加えることができるのはなぜですか?

関数を扱っていますT(n) = 2n + 2

nT(n) <= c * f(n)が大きくなるような ac を見つけたい

と があるので、必要T(n) = 2n + 2ですf(n) = n2n + 2 <= c * n

cについて解いて2 + 2/n

2/nは n = 0 では定義されていないため、 を選択しt >= 1ます。を選ぶt=1ので、c=4

誘導による証明:

結論: 2n + 2 ∈ O(n)

与えられた G = {a, b, c, d}, {S, X, Y}, S, {S->XY, X->aXb, X->ab, Y->cYd, Y->cY, Y ->cd}}

|w|c-|w|d+|w|a≥|w|b であることを証明してください

|w|a は、文字列に含まれる 'a' の数です。これは、y->cY を使用して 'd' なしで 'c's を作成できる一方で、ac を作成せずに ad を作成する生産規則がないため、'd's よりも多くの (または同じ量の) 'c's があることを意味します。導出ステップ数の帰納法を使用してこれを正式に証明する必要があり、一日中試みています。どんな助けでも感謝します。

私は構造帰納法によって次のステートメントを証明しようとしています:

ただし、foldr を定義する方法さえわからないため、定義が提供されていないため行き詰まっています。私は今、foldrを次のように定義できると信じています

ここで、空のリストをfoldrに渡す基本ケースの作業を開始したいと思います。私はこれを持っていますが、それが正しいとは思いません。

今、これは私の帰納的なステップのために持っているものです:

この証明が有効かどうかはわかりません。それが正しいかどうか、そうでない場合はどの部分が正しくないかを判断するのに助けが必要です。

構造帰納法を使用して、以下のステートメントで「ns」を証明しようとしています。すべてのリスト'ns'は[Int]型であり、すべての 'm'はInt型です。

定義:

誰かがこれについて私を助けてくれれば幸いです。