0
$\begingroup$

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$.]

$\endgroup$
5
  • $\begingroup$ There should be a starting condition. Which is the first element? $a_1$? $a_0$? Do you have an initial value for it? $\endgroup$
    – Kevin
    Nov 28, 2013 at 7:35
  • $\begingroup$ Your sum, which is fairly close to right, is a geometric series. $\endgroup$ Nov 28, 2013 at 7:36
  • $\begingroup$ I apologize for not providing the starting conditions. $a_1=0, a_2=6$. $\endgroup$
    – tychicus
    Nov 28, 2013 at 7:56
  • $\begingroup$ 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}$. $\endgroup$
    – tychicus
    Nov 28, 2013 at 8:13
  • $\begingroup$ 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. $\endgroup$
    – Kevin
    Nov 28, 2013 at 8:18

1 Answer 1

1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – tychicus
    Nov 28, 2013 at 8:52
  • $\begingroup$ 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$. $\endgroup$
    – tychicus
    Nov 28, 2013 at 9:01
  • $\begingroup$ I corrected my answer taking into account the initial conditions provided $\endgroup$
    – Kevin
    Nov 28, 2013 at 9:43

You must log in to answer this question.

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