2
$\begingroup$

Solve the recurrence $b_1 = 2$ for $$b_n = 3b_{n-1} + 5$$

I've tried solving this problem using iteration, but the formula I get in the end is wrong. It is not a closed formula since there's still recurrence. I think my error is starts from the last line below. I'm not sure how to fix it. The formula I get in the end is:

$2(3^{n-1})+ 5((3^n - 1) / 3)$

which I got by setting $k = n -1$ and using $\sum_{k=0}^{n-1}3^k\ = (3^n-1)/2$

\begin{align*} b_n&=3b_{n-1}+5\\ &=3(3b_{n-2}+5)+5\\ &=3^2b_{n-2}+3\cdot5+5\\ &=3^2(3b_{n-3}+5)+3\cdot5+5\\ &=3^3b_{n-3}+3^2\cdot5-3\cdot5+5\\ &\;\vdots\\ &=3^kb_{n-k}+3^{k-1}\cdot5+3^{k-2}\cdot5+\ldots+3\cdot5+5\\ \end{align*}

$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

Let $a_{n} = b_n+c$ for some $c$ so that $a_{n+1}=3a_n$ (i.e. $a_n$ is geometric sequence). Then $$ a_{n+1}-c= 3a_n-3c+5\implies c = 5/2$$ and $$a_n= a_03^n$$ so $$ b_n = a_03^n-5/2$$

Since $b_1 = 2$ we get $3a_0=9/2$ so $a_0 =3/2$ so we finaly have $$ b_n = {3^{n+1}-5\over 2}$$

$\endgroup$
5
  • $\begingroup$ I thought about your solution for a couple minutes trying to figure out how you got the final answer in the end, but I just can't understand the second line. How did you get the $-3c+5$ part? And how did you conclude that $c=5/2$? $\endgroup$
    – M. Roshid
    Mar 14, 2019 at 16:30
  • 1
    $\begingroup$ alternatively, you can write: $b_n+c=3(b_{n-1}+c), 2c=5 \Rightarrow b_n+5/2=3(b_{n-1}+5/2)$. $\endgroup$
    – farruhota
    Mar 14, 2019 at 16:49
  • 1
    $\begingroup$ The second line comes from substituting $b_n = a_n -c $ into the recurrence $b_{n+1} = 3b_n +5$. Solve for $c$ by substituting $a_{n+1} = 3a_n$ $\endgroup$
    – WW1
    Mar 14, 2019 at 16:53
  • $\begingroup$ Ohhh I understand now. I was confused about c, but now I realize that it is just some constant Maria stated. Thank you very much for clarifying. $\endgroup$
    – M. Roshid
    Mar 14, 2019 at 16:56
  • $\begingroup$ Which answer wil you accept? $\endgroup$
    – nonuser
    Mar 14, 2019 at 20:18
2
$\begingroup$

Put $k =n-1$ and you get, \begin{align}b_n &= 3^{n-1}b_1 + 3^{n-2} \cdot 5 + 3^{n-3} \cdot 5 + \dots +5 \\ &= 2 \cdot 3^{n-1} + 5(1 + 3 + 3^2 + \dots + 3^{n-2}) \\ &= 2\cdot 3^{n-1} + 5\left( \frac{3^{n-1}-1}{2}\right)\\ &= \frac{3^{n+1}-5}{2} \end{align}

$\endgroup$
1
  • $\begingroup$ After seeing your work, I realized that my mistake was when I had substituted in the $3^k$ sigma part, I had written $3^n$ intead of $3^{n-1}$, giving me the wrong equation in the end. Thank you very much! $\endgroup$
    – M. Roshid
    Mar 14, 2019 at 16:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .