2
$\begingroup$

Working with recurring sequences and generating functions, I'm generally lost on solving a general expression of $a_n$ for any $n$ when the next part of the sequence, that is $a_{n+1}$, is in the form of an exponent, such that $a_n = a_{n-1} +k^{n-1}$, where k is some constant. I have no clue on how to approach this problem.

I've solved the Fibonacci sequence by subtracting the two pervious terms and shifting the sequence, but it does not seem to work here.

I'm particularly working with $a_n = 2a_{n-1} + 5^{n-1}$, but the sequence expands extremely fast. The base case, $a_{0} = 1$.

Any help would be appreciated!

$\endgroup$
2
  • $\begingroup$ In the two examples you mention, it is often done in two parts. First the general soluion to the homogeneous equation. Second, a particular solution ( either by undetermined coefficients or variation of parameters or some other ad-hoc method ). $\endgroup$
    – GEdgar
    Nov 10, 2020 at 1:22
  • $\begingroup$ @GEdgar The way I've solved the Fibonacci sequence was by declaring $a_n$ as $F(x)$ and then subtracting $xF(x)$ and subtracting $x^2F(x)$, setting the entire difference equal to 1, and getting the generator function of $1/(1-x+x^2)$. No clue how to proceed here, though. $\endgroup$ Nov 10, 2020 at 1:25

4 Answers 4

4
$\begingroup$

Because the one with which you’re now working is first-order, you can simply ‘unwind’ it:

$$\begin{align*} a_n&=2a_{n-1}+5^{n-1}\\ &=2\left(2a_{n-2}+5^{n-2}\right)+5^{n-1}\\ &=2^2a_{n-2}+2\cdot5^{n-2}+5^{n-1}\\ &=2^2\left(2a_{n-3}+5^{n-3}\right)+2\cdot5^{n-2}+5^{n-1}\\ &=2^3a_{n-3}+2^2\cdot5^{n-3}+2\cdot5^{n-2}+5^{n-1}\\ &\;\;\vdots\\ &=2^ka_{n-k}+\sum_{i=0}^{k-1}2^i5^{n-1-i}\\ &\;\;\vdots\\ &=2^na_0+\sum_{i=0}^{n-1}2^i5^{n-1-i}\\ &=2^na_0+5^{n-1}\sum_{i=0}^{n-1}\left(\frac25\right)^i\\ &=2^na_0+5^{n-1}\cdot\frac{1-\left(\frac25\right)^n}{1-\frac25}\\ &=2^na_0+\frac{5^n-2^n}3 \end{align*}$$

$\endgroup$
3
  • $\begingroup$ At first I was a bit lost regarding the pattern, but now that I understand it, it is a much faster approach than using generating functions. Thank you! $\endgroup$ Nov 10, 2020 at 7:18
  • 1
    $\begingroup$ @ViolettaBlejder For a faster approach please see my answer and read the link to my other post to get a better understanding. $\endgroup$
    – Neat Math
    Nov 10, 2020 at 15:32
  • $\begingroup$ @ViolettaBlejder: You’re welcome! $\endgroup$ Nov 10, 2020 at 18:34
2
$\begingroup$

I love to telescope.

If $a_n = ua_{n-1} + vc^{n} $, then $\dfrac{a_n}{u^n} = \dfrac{a_{n-1}}{u^{n-1}} + v(c/u)^{n} $.

Let $b_n = \dfrac{a_n}{u^n}$. Then $b_n =b_{n-1}+vd^n $ where $d = c/u$.

Then $b_n-b_{n-1} =vd^n $.

Summing,

$\begin{array}\\ b_m-b_0 &=\sum_{n=1}^m (b_n-b_{n-1})\\ &=\sum_{n=1}^m vd^n\\ &=v\dfrac{d-d^{m+1}}{1-d}\\ &=vd\dfrac{1-d^{m}}{1-d}\\ \end{array} $

so

$\begin{array}\\ \dfrac{a_m}{u^m} &=a_0+vd\dfrac{1-d^m}{1-d}\\ \text{or}\\ a_m &=a_0u^m+\dfrac{vc}{u}u^m\dfrac{1-(c/u)^m}{1-c/u}\\ &=a_0u^m+vc\dfrac{u^m-c^m}{u-c}\\ &=a_0u^m+vc\dfrac{u^m-c^m}{u-c}\\ \end{array} $

In this case, $u=2, c=5, v = \frac15, a_0 = 1 $ so $a_m = 2^m + \dfrac{2^m-5^m}{2-5} = 2^m + \dfrac{5^m-2^m}{3} $.

This can be rewritten as

$\begin{array}\\ a_m &=a_0u^m+vc\dfrac{u^m-c^m}{u-c}\\ &=\dfrac{(u-c)a_0u^m+vc(u^m-c^m)}{u-c}\\ &=\dfrac{(a_0(u-c)+vc)u^m-vc^{m+1}}{u-c}\\ \end{array} $

Again, we get $=\dfrac{(a_0(u-c)+vc)u^m-vc^{m+1}}{u-c} =\dfrac{(-3+1)2^m-5^{m}}{-3} =\dfrac{2\cdot 2^m+5^{m}}{3} $.

$\endgroup$
1
$\begingroup$

We use ordinary generating functions. Let $A(x) = \sum_{i=0}^n a_n x^n$. Then we have (summing from $n=1$)

\begin{align} a_n &= 2a_{n-1} + 5^{n-1},\\ \sum_{n=1}^\infty a_nx^n &= \sum_{n=1}^\infty 2a_{n-1} x^n + \sum_{n=1}^\infty 5^{n-1} x^n,\\ A(x) - a_0 &= 2x\sum_{n=1}^\infty a_{n-1} x^{n-1} + x\sum_{n=1}^\infty 5^{n-1} x^{n-1},\\ A(x) - 1 &= 2x\sum_{n=0}^\infty a_{n} x^{n} + x\sum_{n=0}^\infty 5^{n} x^{n},\\ A(x) - 1 &= 2xA(x) + \frac{x}{1-5x},\\ A(x) - 2xA(x) &= \frac{x}{1-5x} + 1,\\ A(x) &= \frac{x}{(1-2x)(1-5x)} + \frac{1}{1-2x}.\\ \end{align} Now we use partial fraction decomposition and a bit of algebra to obtain

\begin{align} A(x) &= \frac{1}{3(1-5x)} - \frac{1}{3(1-2x)} + \frac{1}{1-2x}\\ &= \frac{1}{3} \left(\frac{1}{(1-5x)} + \frac{2}{(1-2x)}\right)\\ &= \frac{1}{3} \left(\sum_{n=0}^{\infty} 5^nx^n + 2\sum_{n=0}^{\infty}2^nx^n \right). \end{align}

From here we see $$a_n = \frac{5^n + 2^{n+1}}{3}.$$

$\endgroup$
3
  • $\begingroup$ This was by far the most understandable explanation for me, as I am currently working with only generating functions, so other things seem a little bizarre. After you helped me decompose into the generating functions, it was really easy to complete the problem, and it seems that I got the correct answer. Thank you! $\endgroup$ Nov 10, 2020 at 7:12
  • $\begingroup$ @ViolettaBlejder You're welcome! I like this particular way of doing things here, but what's enlightening about the other answers (such as Brian M. Scott's) is that this powerful machinery is not always necessary. $\endgroup$
    – Hendrix
    Nov 10, 2020 at 14:17
  • $\begingroup$ The standard way to approach it using generating functions is to first make it homogeneous: $a_{n+1}-2a_n=5(a_n-2a_{n-1})$ then follow the steps in this post: math.stackexchange.com/questions/3899926/… $\endgroup$
    – Neat Math
    Nov 10, 2020 at 15:25
1
$\begingroup$

First make it homogeneous.

$$a_n-2a_{n-1} = 5^{n-1} $$ $$a_{n+1}-2a_n = 5^n $$ $$\Rightarrow a_{n+1}-2a_n=5(a_n-2a_{n-1}) \tag 1$$ $$\Rightarrow a_{n+1}-5a_n=2(a_n-5a_{n-1}) \tag 2$$

Both (1) and (2) are geometric sequences, so

$$ a_{n+1}-2a_n = 5^n (a_1-2a_0) = 5^n (3-2)= 5^n \tag 3 $$ $$ a_{n+1}-5a_n = 2^n (a_1-5a_0) = 2^n (3-5)= -2^{n+1} \tag 4 $$ (3)-(4) $$ a_n = \frac{1}{3} (5^n + 2^{n+1}). \blacksquare $$

(Please see my post Show that for every positive integer $ f_n=\frac{\left ( \frac{1+\sqrt5}{2} \right )^n-\left ( \frac{1-\sqrt5}{2} \right )^n}{\sqrt5}$)

$\endgroup$
1
  • $\begingroup$ If we start from a homogeneous second order equation we need to derive (3). Here it's already given in the original problem. I put it there just for illustration purpose. $\endgroup$
    – Neat Math
    Nov 10, 2020 at 2:43

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.