1
$\begingroup$

Consider the following two sequences:

$$a_n = 3a_{n-1} + 2a_{n-2}, a_0 = 1, a_1 = 2$$ and $$a_n = 2a_{n-1} + 4^{n-1}, a_0 = 1$$

I see the method used here that looks nice and clean but I can't detect the pattern here in these two cases. Maybe I'm not paying good attention?

$\endgroup$
  • $\begingroup$ The examples used in your link are all functions, not recursive relations. If you can convert your recursive relations into functions, then you can use your link. $\endgroup$ – Toby Mak Feb 21 '18 at 8:10
1
$\begingroup$

As regards the second one, multiply both sides of the equation by $z^n$ and take the sum for $n$ from $1$ to infinity: $$\sum_{n=1}^{\infty}a_nz^n = 2\sum_{n=1}^{\infty}a_{n-1}z^n + \sum_{n=1}^{\infty}4^{n-1}z^n,$$ that is, for $4|z|<1$, $$f(z)-a_0 = 2zf(z) + z\sum_{n=1}^{\infty}(4z)^{n-1}=2zf(z) + \frac{z}{1-4z}$$ where $f(z):=\sum_{n=0}^{\infty}a_nz^n$ is the generating function of the sequence $(a_n)_{n\geq 0}$. Finally use the fact that $a_0=1$, and solve with respect to $f$.

Can you take it from here? For the first one, try to follow the same procedure.

$\endgroup$
  • $\begingroup$ yes. thank you very much. $\endgroup$ – B.Li Feb 21 '18 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.