0

Solve the recurrence $h_{n+2} - 2h_{n+1} + h_n = {n \choose 2} + 2^n$ where $n \geq 0$, with initial values $h_0$ = 1 and $h_1$ = 1.

I tried solving this question by writing $h_{n+3}$ term as $h_{n+3} - 2h_{n+2} + h_{n+1} = {n+1 \choose 2} + 2^{n+1}$ and subtracted both the equations after multiplying the original equation by $2$ so that the $2^{n+1}$ term gets cancelled out. Now I am left with an expression which has all the terms $h_{n+3}, h_{n+2}, h_{n+1}, h_{n}$ on the LHS and a quadratic equation of $n$ on the RHS. I don't know how to proceed further so that I end up with an equation of $h_{n}$ only in terms of $n$.

jvdhooft
  • 7,589
  • 9
  • 25
  • 47
vk1234
  • 25

1 Answers1

0

$$h_{n+2}-2h_{n-1}+h_n=n(n-1)/2+2^n~~~~(1)$$ First we solve $$h_{n+2}-2h_{n-1}+h_n=0~~~~~~~(2)$$, by taking $h(n)=t^n$ we get $t=1,1$ So $$h(n)=(C_1+C_2 ~n)1^n~~~~(3)$$ Next, we solve $$h_{n+2}-2h_{n-1}+h_n=n(n+1)/2~~~~(4)$$ The HS is second difference of $h(n)$ and RHS is a quadratic of $n$, therefore $h(n)$ in general needs to be a ploynomial of degree four as $$h(n)=an^4+bn^3+cn^2+dn+e~~~~~(5)$$ inserting it in (4) we get, $$12an^2+(24a+6b)n~+4a+6b+2c=\frac{n^2}{2}-\frac{n}{2}~~~~(6)$$ Comparing various coefficients of various powers of $n$ in (6), we get $a=1/24, b=-1/4,c=11/24$. Hence the solution of (4) is $$ h(n)=\frac{n^4}{24}-\frac{n^3}{4}+\frac{11n^2}{24}+dx+e~~~~~(7)$$ Next, we solve $$h_{n+2}-2h_n+h_n=2^n~~~~(8)$$ Let $h(n)=k 2^n$ in (8), to get $k=1$. Finally, the total solution of (1) is $$h(n)=C_1+C_2~n+\frac{n^4}{24}-\frac{n^3}{4}+\frac{11n^2}{24}+2^n$$ $d$ and $e$ of (7) have been absorbed in $C_1$ and $C_2$, respectively.

Z Ahmed
  • 43,235