Solve the nonhomogeneous recurrence relation hn4hn1 4hn23n 1

Solve the nonhomogeneous recurrence relation hn=4h(n-1) -4h(n-2)+3n +1, h0=1, h1=2

First we solve the homogeneous recurrence assoaciated with problem

hn=4h(n-1)-4h(n-2)

It is linear homogneous with constant coefficients so we look for hn=r^n

Substituting gives

r^2-4r+4=0

r=2, repeated root

SO general solution is

hn=2^n(A+Bn)

For the inhomogneous we guess a particular solution based on inhomogenous part ie 3n+1

LEt, An+B be the guess

Substituting gives

An+B=4A(n-1)+4B-4A(n-2)-4B+3n+1

An+B=4A+3n+1

Hence, A=3, B=4A+1=13

hn=3n+13

hn=2^n(A+Bn)+3n+13

h0=A+13=1

A=-12

hn=2^n(-12+Bn)+3n+13

h1=2(-12+B)+16=2

2(-12+B)=-14

-12+B=-7

B=5

hn=2^n(-12+5n)+3n+13