漸化式

　　合計＝２^n-1・（ｎ，ｋ＋１）＋２ｎ・ｆ（ｎ−１，ｋ）

　　ｆ（ｎ，０）＝合計／２ｎ

　　ｆ（ｎ，１）＝合計／ｎ

　　ｆ（ｎ，ｋ）＝合計／（ｎ−ｋ），ｋ＝２〜ｎ−１

の形で与えられる．漸化式を解いてみよう．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】ｋ＝０の場合

　　ｆ（ｎ，０）＝｛２^n-1・（ｎ，１）＋２ｎ・ｆ（ｎ−１，０）｝／２ｎ

　　ｆ（ｎ，０）＝｛２^n-1・ｎ＋２ｎ・ｆ（ｎ−１，０）｝／２ｎ

　　ｆ（ｎ，０）＝２^n-2＋ｆ（ｎ−１，０）

　　ｆ（ｎ，０）−ｆ（ｎ−１，０）＝２^n-2

　　ｆ（ｎ−１，０）−ｆ（ｎ−２，０）＝２^n-3

　　ｆ（３，０）−ｆ（２，０）＝２

　　ｆ（ｎ，０）−ｆ（２，０）＝２＋・・・＋２^n-2＝２（２^n-2−１）

　　ｆ（ｎ，０）＝２^n-1

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】ｋ＝１の場合

　　ｆ（ｎ，１）＝｛２^n-1・（ｎ，２）＋２ｎ・ｆ（ｎ−１，１）｝／ｎ

　　ｆ（ｎ，１）＝｛２^n-2・ｎ（ｎ−１）＋２ｎ・ｆ（ｎ−１，１）｝／ｎ

　　ｆ（ｎ，１）＝２ｆ（ｎ−１，１）＋２^n-2（ｎ−１）

　　２ｆ（ｎ−１，１）＝４ｆ（ｎ−２，１）＋２^n-2（ｎ−２）

　　２^n-3ｆ（３，１）＝２^n-2ｆ（２，１）＋２n-2・２

　　ｆ（ｎ，１）＝２^n-2＋２^n-2｛（ｎ−１）ｎ／２−１｝

　　ｆ（ｎ，１）＝２^n-2（ｎ−１）ｎ／２

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【３】ｋ＝ｎ−１の場合

　　ｆ（ｎ，ｎ−１）＝２^n-1・（ｎ，ｎ）＋２ｎ・ｆ（ｎ−１，ｎ−１）＝２^n-1＋２ｎ

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝