# Recurrence relation - How is the auxiliary relation found?

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}$$)

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?

$$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.$$
• That's a beautiful solution, solving recurrence relation by parts. Only a little part to mention: $A_{1}=2$, so $α = -1$. Sep 21, 2020 at 10:59
• 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$ Sep 26, 2020 at 23:29