问题：

利用生成函数求解下列递推关系

---

---

答案：

令g(x)=h 0 +h 1 x+h 2 x 2 +…+h n x n +… g(x)=h 0 +h 1 x+h 2 x 2 +…+h n x n +… 则 -4x 2 g(x)=-4h 0 x 2 -…-4h n-2 x n +… 将两式相加，并利用h 0 =0，h 1 =1，得 所以 $由 g(x)=h 0 +h 1 x+h 2 x 2 +…+h n x n +… -xg(x)=-h 0 x-h 1 x 2 -…-h n-1 x n -… -x 2 g(x)=-h 0 x 2 -…-h n-2 x n -… 相加并利用h 0 =1，h 1 =3，得 x 2 +x-1=0的根为 分式分解g(x)，得 所以 $由 g(x)=h 0 +h 1 x+h 2 x 2 +h 3 x 3 +…+h n x n +… -xg(x)=-h 0 x-h 1 x 2 -h 2 x 3 -…-h n-1 x n -… -9x 2 g(x)=-9h 0 x 2 -9h 1 x 3 -…-9h n-2 x n -… 9x 3 g(x)=9h 0 x 3 +…+9h n-3 x n +… 相加并利用h 0 =0，h 1 =1，h 2 =2，得 所以 $由 g(x)=h 0 +h 1 x+h 2 x 2 +…+h n x n +… -8xg(x)=-8h 0 x-8h 1 x 2 -…-8h n-1 x n -… 16x 2 g(x)=16h 0 x 2 +…+16h n-2 x n +… 相加并利用h 0 =-1，h 1 =0，得 所以 h n =(n-1)4 n $由 g(x)=h 0 +h 1 x+h 2 x 2 +h 3 x 3 +…+h n x n +… -3x 2 g(x)=-3h 0 x 2 -3h 1 x 3 -…-3h n-2 x n -… 2x 3 g(x)=2h 0 x 3 +…+2h n-3 x n +… 相加并利用h 0 =1，h 1 =0，h 2 =0，得 所以 $由 g(x)=h 0 +h 1 x+h 2 x 2 +h 3 x 3 +h 4 x 4 +…+h n x n +… -5xg(x)=-5h 0 x-5h 1 x 2 -5h 2 x 3 -5h 3 x 4 -…-5h n-1 x n -… 6x 2 g(x)=6h 0 x 2 +6h 1 x 3 +6h 2 x 4 +…+6h n-2 x n +… 4x 3 g(x)=4h 0 x 3 +4h 1 x 4 +…+4h n-3 x n +… -8x 4 g(x)=-8h 0 x 4 -…-8h n-4 x n -… 相加并利用h 0 =0，h 1 =1，h 2 =1，h 3 =2，得 - 所以