■太鼓の形は聞こえない(その11)

 漸化式

  合計=2^n-1・(n,k+1)+2n・f(n−1,k)

  f(n,0)=合計/2n

  f(n,1)=合計/n

  f(n,k)=合計/(n−k),k=2〜n−1

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

===================================

【1】k=0の場合

  f(n,0)={2^n-1・(n,1)+2n・f(n−1,0)}/2n

  f(n,0)={2^n-1・n+2n・f(n−1,0)}/2n

  f(n,0)=2^n-2+f(n−1,0)

  f(n,0)−f(n−1,0)=2^n-2

  f(n−1,0)−f(n−2,0)=2^n-3

  f(3,0)−f(2,0)=2

  f(n,0)−f(2,0)=2+・・・+2^n-2=2(2^n-2−1)

  f(n,0)=2^n-1

===================================

【2】k=1の場合

  f(n,1)={2^n-1・(n,2)+2n・f(n−1,1)}/n

  f(n,1)={2^n-2・n(n−1)+2n・f(n−1,1)}/n

  f(n,1)=2f(n−1,1)+2^n-2(n−1)

  2f(n−1,1)=4f(n−2,1)+2^n-2(n−2)

  2^n-3f(3,1)=2^n-2f(2,1)+2n-2・2

  f(n,1)=2^n-2+2^n-2{(n−1)n/2−1}

  f(n,1)=2^n-2(n−1)n/2

===================================

【3】k=n−1の場合

  f(n,n−1)=2^n-1・(n,n)+2n・f(n−1,n−1)=2^n-1+2n

===================================