# Recurrence relation - repeated substitution

I am having some trouble with solving a recurrence relation with repeated substitutions.

$$a_n = 3\cdot2^{n-1}-a_{n-1}$$

I show some work:

$$a_n = 3\cdot2^{n-1} -(3\cdot2^{n-2}-a_{n-2})=3\cdot2^{n-1}-3\cdot2^{n-2}+a_{n-2}$$

Then I guess the pattern looks like this:

$$a_n = 3\cdot\sum_{i=1}^{n}(-1)^{i}\cdot2^{n-i}$$.

But here I am stuck. How can I deal with the summation (given that I am correct so far)?

[Another way to solve it is to manipulate it into $a_n=a_{n-1}+2_{n-2}$ and then solve it with the auxiliary equation method to get $a_n=2(-1)^n+2^n$.]

• There should be a starting condition. Which is the first element? $a_1$? $a_0$? Do you have an initial value for it? Nov 28, 2013 at 7:35
• Your sum, which is fairly close to right, is a geometric series. Nov 28, 2013 at 7:36
• I apologize for not providing the starting conditions. $a_1=0, a_2=6$. Nov 28, 2013 at 7:56
• I guess the summation should go from $1$ to $n-2$ if I am correct: $\sum_{i=1}^{n-2}(-1)^i\cdot2^{n-i}$. Nov 28, 2013 at 8:13
• I'm sorry, I didn't see your reply while I was writing the answer. I believe you could still adapt it to your problem. Nov 28, 2013 at 8:18

$$a_1 = 0$$ $$a_2 = 3\cdot2^1-a_1 = 6$$ Since it seems you don't have problem guessing the pattern, then I will jump there. Hypothesis: $$a_n=3\sum_{i=1}^{n-1}(-1)^{n-i-1}2^i$$ Proof: we can tell by inspection that it works for $n=1$. Let's assume it works for $n=k$. For $n=k+1$: $$a_{k+1}=3\cdot2^k-a_k=3\cdot2^k-\left(3\sum_{i=1}^{k-1}(-1)^{k-i-1}2^i\right)$$ $$=3\cdot2^k-3\sum_{i=1}^{k-1}(-1)^{k-i-1}2^i$$ $$=3\cdot(-1)^{(k+1)-k-1}2^k+3\sum_{i=1}^{k-1}(-1)^{(k+1)-i-1}2^i$$ $$=3\sum_{i=1}^{k}(-1)^{(k+1)-i-1}2^i=3\sum_{i=1}^{n-1}(-1)^{n-i-1}2^i$$ Which completes the proof. Next, comes the simplification: $$a_n=3\sum_{i=1}^{n-1}(-1)^{n-i-1}2^i=3\sum_{i=1}^{n-1}(-1)^{n-i-1}(-1)^{2i}2^i=3(-1)^{n-1}\sum_{i=1}^{n-1}(-1)^{i}2^i=3(-1)^{n-1}\sum_{i=1}^{n-1}(-2)^i=6(-1)^{n}\sum_{i=1}^{n-1}(-2)^{i-1}=6(-1)^{n}\sum_{i=0}^{n-2}(-2)^i=6(-1)^{n}\frac{(-2)^{n-1}-1}{(-2)-1}=2(-1)^{n-1}((-2)^{n-1}-1)=2^n+2(-1)^{n}$$
• Thank you but I am not quite sure yet how to arrive at the solution. I do some more work: $a_1=0, a_2=6, a_3=3\cdot2^2-a_2$. Then I compute $a_n = 3\cdot2^{n-1}-3\cdot2^{n-2} + 3\cdot2^{n-3} + ... +(-1)^{?}(3\cdot2^{2}-a_2)$. I wonder if I whould use the summation $1 + (-2)^1+(-2)^2+...+(-2)^{n-1}=1\cdot\frac{1-(-2)^n}{1-(-2)}$?. But then I have to remove 1 and $(-2)^1$ I guess from the formula. Nov 28, 2013 at 8:52
• The formula would be something like $a_n=3\cdot(\frac{1-(-2)^{n}}{3}-1-(-2)^1) = 4-(-2)^{n}=2^2-(-2)^n$. Nov 28, 2013 at 9:01