Answer to Question #275556 in Discrete Mathematics for Himanshi

Question

Determine values of the constants A and B such that an = An + B is a solution of

recurrence relation an = 2an−1 + n + 5. Hence, find the solution of this recurrence

relation with a0 = 4.

Answer 1

Let us determine values of the constants $A$ and $B$ such that $a_n = An + B$ is a particular solution of the recurrence relation $a_n = 2a_{n−1} + n + 5.$

It follows that

$An+B=2(A(n-1)+B)+n+5=2An-2A+2B+n+5$

$=(2A+1)n+(2B-2A+5),$

and thus

$A=2A+1$ and $B=2B-2A+5.$

Therefore, $A=-1$ and $B=2A-5=-7.$

We conclude that $a_n=-n-7$ is a paticular solution of the recurrence relation.

Further, let us find the general solution of this recurrence relation with $a_0 = 4.$

It follows that the characteristic equation $k-2=0$ has the solution $k=2,$ and hence the general solution is of the form $a_n=C\cdot2^n-n-7.$ Since $4=a_0=C-7,$ we conclude that $C=11.$

Consequently, the general solution of this recurrence relation $a_n = 2a_{n−1} + n + 5$ with $a_0 = 4$ is

$a_n=11\cdot2^n-n-7.$