私の知る限り、漸化式を解くには4つの方法があります。1-漸化式ツリー2-置換3-反復4-微分
Substitutionを使用するように求められます。これは、出力の式を推測する必要があります。CLRSの本から、これを行うための魔法はないことを読みました。これを行うためのヒューリスティックがあるかどうか興味がありましたか？
繰り返しツリーを描画するか、反復を使用することで確かにアイデアを得ることができますが、出力はBig-OHまたはTheta形式になるため、数式は必ずしも一致しません。
置換を使用して漸化式を解くための推奨事項はありますか？
漸化式を解くための可能な方法のリストは完全ではないことに注意してください。それらはほとんどの問題を解決する可能性が高いため、コンピューター科学者に教えるツールのセットにすぎません。
漸化式の正確な解法については、数学者は母関数と呼ばれるツールを使用します。母関数は正確な解を与え、一般にマスター定理よりも強力です。
ここについて学ぶための素晴らしいリソースがオンラインにあります。http://www.math.upenn.edu/~wilf/DownldGF.html
最初のいくつかの例を実行すると、すぐにコツをつかむことができます。
数学のバックグラウンドが必要で、基本的なテイラー級数を理解している必要があります。http://en.wikipedia.org/wiki/Taylor_series
母関数も確率において非常に役立ちます。
単純なものについては、「合理的な」推測をしてください。
より複雑なものについては、先に進んで繰り返しツリーを使用します—推測を生成するための最も簡単な「アルゴリズム」であるように思われます。境界を証明するために繰り返しツリーを使用するのは難しい場合があることに注意してください（詳細を正しく理解するのは困難です）。漸化式ツリーは、推測を形成するのに非常に役立ちます。推測は、置換によって証明されます。
数式がBig-OまたはThetaの出力と一致しないと言っている理由がわかりません。それらは通常正確には一致しませんが、それはBig-Oのポイントの一部です。置換に戻る秘訣の一部は、置換代数を機能させるためにBig-Oソリューションをプラグインする方法を知ることです。IIRC、CLRSは、この1つか2つの例を実行します。