0
$\begingroup$

Here is a recurrence relation.

$a_{1}=2, n=1$

$a_{n}=2a_{n-1}+3*2^{n-1}-1, n>=2$

I've already known that the follow method allows finding the general term of $a_{n}$.

$a_{n}=2a_{n-1}+3*2^{n-1}-1$ (multiply both sides by $2^{0}$)

$a_{n-1}=2a_{n-2}+3*2^{n-2}-1$ (multiply both sides by $2^{1}$)

$a_{n-2}=2a_{n-3}+3*2^{n-3}-1$ (multiply both sides by $2^{2}$)

...

$a_{2}=2a_{1}+3*2^{1}-1$ (multiply both sides by $2^{n-2}$)

$a_{1}=2$ (multiply both sides by $2^{n-1}$)

(add all those above together)

However, there is another way, let $b_{n}=a_{n}-3n*2^{n-1}-1$, then we will find out that $b_{n}=2b_{n-1}$, then calculate $b_{n}$, and get $a_{n}$

How is the auxiliary relation found? Is there a specific way?

$\endgroup$

2 Answers 2

0
$\begingroup$

$$A_n=2A_{n-1}+3. 2^{n-1}-1~~~~(1)$$, Take the homogeneous part: $A_n=2A_{n-1}=0~~~(2)$, by telescopic multiplication of $A_1=2 A_{0}, A_{2}= 2A_{3}, A_{3}=2 A_{2},....., A_n=2 A_{n-1}$, we get $A_n= \alpha 2^{n}.$ Next, take $A_n-2 A_{n-1}= 3. 2^{n-1}...(3)$ In this let $A_n=\beta n 2^n$, then $\beta n 2^n -\beta n 2^n+\beta 2^n=3. 2^{n-1} \implies \beta =3/2.$ Next we solve $A_n-2A_{n-1}=-1,$ taking $A_n=\gamma \implies \gamma- 2\gamma=-1 \implies \gamma=1.$ So now we have $A_n=\alpha 2^n+3n 2^{n-1}+1$, finally using $A_1=1$, we get $\alpha--3/2$. Hence $$A_n=-3.2^{n-1}+3n2^{n-1}+1$$

Edit: As pointed by @Steven Liang that $A_1=2$ so $\alpha=1$, so the correct answer is: $$A_n=-2^{n}+3n2^{n-1}+1.$$

$\endgroup$
3
  • 1
    $\begingroup$ That's a beautiful solution, solving recurrence relation by parts. Only a little part to mention: $A_{1}=2$, so $α = -1$. $\endgroup$ Sep 21, 2020 at 10:59
  • $\begingroup$ Oh! yes, I over sighted this. $\endgroup$
    – Z Ahmed
    Sep 21, 2020 at 11:13
  • $\begingroup$ If $a_{n+1}=-3a_{n}+4*7^{n}+5$, when considering $β$ in the 2nd step, should we assume $a_{n}=α(-3)^{n}+β7^{n}$? Is that the correct form and the only possible expression? Combined with $a_{1}=2$, I get $a_{n}=41/60*(-3)^{n}+2/5*7^{n}+5/4$ $\endgroup$ Sep 26, 2020 at 23:29
0
$\begingroup$

This is a linear inhomogeneous recurrence with constant coefficients. The method of first solving the homogeneous equation and then generating the general solution is detailed in Wikipedia

$\endgroup$
1
  • $\begingroup$ That's a detailed source of information. Many thanks for the help. $\endgroup$ Sep 21, 2020 at 15:34

You must log in to answer this question.

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