solve recurrence relation $a_n = 6 a_{n–1} – 9 a_{n–2}$, where $a_0 = 1$ and $a_1 = 6$ and Verify, using Principle of Mathematical Induction, that $a_n = 3^n + n 3^n$.

ans: i have done so far...
put $a_n=b_n$
$b^2-6b+9=0$, $b=3,3$

general solution: $a_n=(c_1+c_2n)3^n$

  • $\begingroup$ Please check to be sure that I guessed right in interpreting your formulas and in supplying the missing value for $a_0$. $\endgroup$ – Brian M. Scott Sep 13 '13 at 7:56
  • 1
    $\begingroup$ I fail to understand the "ans" paragraph. Aren't you asked to use mathematical induction? (Presumably, on $n$... So, the beginning of the proof should read something like "Let $n=0$. The property holds because... Then...") $\endgroup$ – Did Sep 13 '13 at 7:57
  • $\begingroup$ @Did: He appears to have been asked both to solve and to verify, the latter using math. ind. $\endgroup$ – Brian M. Scott Sep 13 '13 at 7:58
  • $\begingroup$ @BrianM.Scott I've altered some of your edit $a_0=1$ and $3^n$ rather than $3n$ $\endgroup$ – Mark Bennet Sep 13 '13 at 7:58
  • $\begingroup$ @Mark: You’re right. (And you and I were editing the $0$ into $1$ simultaneously after you corrected the $3n$.) $\endgroup$ – Brian M. Scott Sep 13 '13 at 7:59

It makes no sense to ‘put $a_n=b_n$’ when you have no $b_n$ in the problem. What you wanted is the auxiliary equation $b^2-6b+9=0$, which you correctly solved to find the general solution


for some constants $c_1$ and $c_2$. You determine those by using the known values of $a_0$ and $a_1$: when $n=0$ equation $(1)$ becomes


and when $n=1$ it becomes


Now simplify $(2)$ and $(3)$ and solve for $c_1$ and $c_2$ to finish deriving the solution.

To verify it by mathematical induction you must do three things:

  1. verify that $3^0+0\cdot3^0=a_0$, i.e., that the formula gives the correct value when $n=0$;
  2. verify that $3^1+1\cdot3^1=a_1$, i.e., that the formula gives the correct value when $n=0$; and
  3. show that if $n\ge 2$ and $a_k=3^k+k3^k$ for $k=0,1,\ldots,n-1$, then $a_n=3^n+n3^n$.

(1) and (2) are the basis steps of your induction, and (3) is the induction step: in it you’re showing that if the expression $3^k+k3^k$ gives the right value for $a_k$ for all $k<n$, then it also gives the correct value for $a_n$. In carrying out this step you’ll use the recurrence that defines the sequence.


If $n=0$ then $a_{0}=1$ and $3^{0}+0=1$ so the formula agrees here.

$a_{1}=6$ by definition and $3^{1}+1\cdot3^{1}=6$ so it is true for $n=1$. Assume this is true for all $k\le n$. We now show this for $n+1$.


$=6\cdot3^{n}+6n\cdot3^{n}-9\cdot3^{n-1}-9(n-1)3^{n-1}=2\cdot3^{n+1}+2n\cdot3^{n+1}-3^{n+1}-(n-1)\cdot 3^{n+1}=3^{n+1}+(n+1)\cdot3^{n+1}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.