Answer to Question #244600 in Discrete Mathematics for Alina

Question

(a) Find the solution to a_n = a_n-1 + 2n + 3 with the initial conditions a₀= 4.

(b) Consider the recurrence a_n = a_n-1 + 2a_n-2 + 2n - 9 show that this recurrence is solved by:

i. a_n = 2 - n

ii. a_n = 2 - n + b * 2ⁿ for any real b.

Answer 1

(a) Characteristic equation:

$k = 1$

Then the general solution of the homogeneous equation:

${\left( {{a_n}} \right)_0} = {C_1} \cdot {1^n} = {C_1}$

We will seek a particular solution in the form

${A_n} = (An + B)n = A{n^2} + Bn \Rightarrow {A_{n - 1}} = A{(n - 1)^2} + B(n - 1)$

Then

$A{n^2} + Bn = A{(n - 1)^2} + B(n - 1) + 2n + 3$

$A{n^2} + Bn = A{n^2} - 2An + A + Bn - B + 2n + 3$

$2An - A + B = 2n + 3 \Rightarrow A = 1,\,B = 4$

Then

${A_n} = {n^2} + 4n$

${a_n} = {\left( {{a_n}} \right)_0} + {n^2} + 4n = {C_1} + {n^2} + 4n$

${a_0} = 4 \Rightarrow {C_1} + {0^2} + 4 \cdot 0 = 4 \Rightarrow {C_1} = 4$

Then

${a_n} = 4 + {n^2} + 4n$

Answer: ${a_n} = 4 + {n^2} + 4n$

(b) ${a_n} = {a_{n - 1}} + 2{a_{n - 2}} + 2n - 9 \Rightarrow {a_n} - {a_{n - 1}} - 2{a_{n - 2}} = 2n - 9$

i. If ${a_n} = 2 - n$ then

${a_n} - {a_{n - 1}} - 2{a_{n - 2}} = 2 - n - (2 - (n - 1)) - 2(2 - (n - 2)) = 2 - n - (3 - n) - 2(4 - n) = 2 - n - 3 + n - 8 + 2n = - 9 + 2n=2n-9$

Then ${a_n} = 2 - n$ is the solution of this recurrence

ii. If ${a_n} = 2 - n + b \cdot {2^n}$ then

${a_n} - {a_{n - 1}} - 2{a_{n - 2}} = 2 - n + b \cdot {2^n} - (2 - (n - 1) + b \cdot {2^{n - 1}}) - 2(2 - (n - 2) + b \cdot {2^{n - 2}}) = 2 - n - (3 - n) - 2(4 - n) + 4b \cdot {2^{n - 2}} - 2b \cdot {2^{n - 2}} - 2b \cdot {2^{n - 2}} = 2 - n - 3 + n - 8 + 2n = 2n - 9$

Then ${a_n} = 2 - n + b \cdot {2^n}$ is the solution of this recurrence