Answer to Question #302920 in Discrete Mathematics for Snave

Question

Let a_{k} = 3^{k} + k - 2 for all k \geq 0.

Write down the values of a_{1}, a_{2} and a_{3}.

Write down the values of A(1), A(2) and A(3) defined by the recurrence relation: A(0) = -1, A(k) = 3A(k - 1) - 2k + 7, k \geq 1

Show that A(k) = a_{k} is a solution of the recurrence relation for all values of k \geq 1.

Answer 1

Given, $a_{k} = 3^{k} + k - 2 ~\forall k \geq 0.$

Then,

$\begin{aligned} a_{1} &= 3^1+1-2=2\\ a_2&=3^2+2-2=9\\ a_3&=3^3+3-2=28 \end{aligned}$.

Given the recurrence relation, $A(k) = 3A(k - 1) - 2k + 7, k \geq 1$ and $A(0) = -1$.

$\begin{aligned} A(1) &= 3A(0) - 2*1+7= -3-2+7=2\\ A(2) &= 3A(1) - 2*2+7=3*2-4+7=9\\ A(3) &= 3A(2)-2*3+7= 3*9-6+7=28 \end{aligned}$

The recurrence relation, $A(k) = 3A(k - 1) - 2k + 7, k \geq 1$ can be written as

$A(k) - 3A(k - 1) = - 2k + 7, k \geq 1$ which is a first order non-homogeneous relation.

The characteristic equation is $a - 3 = 0$. The root is $a=3$. Hence the homogeneous solution is $A_h(k) = c\cdot3^k$.

Since the R.H.S of the given relation is $-2k+7$, the particular solution is of the form $d_0 + d_1 k$.

Using this in the given relation we get,

$\begin{aligned} (d_0 + d_1 k) - 3(d_0 + d_1 (k-1)) &= 7 - 2k\\ d_0 + d_1 k - 3d_0 - 3d_1k +3d_1 &= 7 - 2k\\ (-2d_0+3d_1)-2d_1k &= 7-2k \end{aligned}$

Equating the corresponding coefficients, we get

$\begin{aligned} -2d_0+3d_1&=7\qquad \qquad \qquad \qquad (1)\\ -2d_1 &= -2 \implies d_1 = 1\\ \end{aligned}\\ \text{Using this in (1), we get~} d_0 = -2$

Hence the particular solution is $A_p(k) = k - 2.$

Therefore, the solution of the recurrence relation is $A(k) = c\cdot 3^k + k - 2$.

Given, A(0) = -1. Using this, we get

$-1=A(0) = c+0-2\implies c = 1$

Hence, $A(k) = 3^k + k - 2$. Thus we proved $a_k$ is the solution of $A(k)$.