3
$\begingroup$

I am wondering whether there is an efficient way to find explicit formulas for non-homogenous recursive sequences.

  • While writing out the first few terms and looking for patterns works sometimes, it is not exactly an amazing approach.
  • It takes a long time and with less obvious patterns in sequences, it is prone to failure.

This has left me wondering whether there is a more systematic approach for the following two types of sequences:

  1. Non-Homogeneous Recursive Sequences with a Constant Term:

Something like $a_n = c_1 a_{n-1} + c,$ where $c$ is constant, such as $a_n = 2a_{n-1} + 1$ with $(a_0 = 1)$.

  1. Non-Homogeneous Recursive Sequences with a Variable Term:

Something like $a_n = c_1 a_{n-1} + n,$ such as $a_n = 2a_{n-1} + n$ with $(a_0 = 1)$.

Preferrably, I'd be looking for some method without the involvement of generating functions.

$\endgroup$
5
  • 2
    $\begingroup$ This is standard stuff, treated in any discrete math textbook. If you have $a_n=ca_{n-1}+f(n)$, then there's a list of forms to try for a solution, depending on the form of $f$; polynomial, exponential, sines and cosines, products and sums of the preceding. $\endgroup$ Commented Jul 8, 2024 at 0:48
  • $\begingroup$ @GerryMyerson It isn't in ours, can you recommend a good chapter & book for me to have a look at? $\endgroup$ Commented Jul 8, 2024 at 9:25
  • $\begingroup$ You might find something useful at the questions listed under "Related" on this page, e.g., math.stackexchange.com/questions/806223/… If there's a university library nearby, they'll have lots of textbooks to choose from. $\endgroup$ Commented Jul 8, 2024 at 12:35
  • 1
    $\begingroup$ Here is an answer of mine that solves this: math.stackexchange.com/questions/4136940/… $\endgroup$ Commented Jul 11, 2024 at 22:00
  • $\begingroup$ @martycohen This is great, thanks! $\endgroup$ Commented Jul 12, 2024 at 23:14

2 Answers 2

Reset to default
2
$\begingroup$

Actually, every non-homogeneous first-order linear recurrence relation, i.e. $a_{n+1} = f_na_n + g_n$, can be solved in a closed form (see here for example). Nonetheless, ansatz methods are often preferred for the sake of simplicity. You can find tables of these online, but you will be able to "feel" them through practice after some time.

$\endgroup$
0
$\begingroup$

I have asked myself the same question, although I had in mind completely arbitrary, even random, parameter and inhomogeneous terms. So this solution was designed primarily for numerical solutions. Here is what I did.

We consider the recurrence relation relation

$$ x_k=a_kx_{k-1}+b_k $$ where the coefficients are arbitrary functions of $k$ and the initial condition is $x_0$. The solution is found by induction as follows:

$$ \begin{align} &x_1=a_1 x_0+b_1\\ &x_2=a_1a_2x_0+a_2b_1+b_2\\ &x_3=a_1a_2a_3x_0+a_2a_3b_1+a_3b_2+b_3\\ &x_4=a_1a_2a_3a_4x_0+a_2a_3a_4b_1+a_3a_4b_2+a_4b_3+b_4\\ &\vdots\\ &x_k=x_0\prod_{j=1}^ka_j+b_1\prod_{j=2}^ka_j+b_2\prod_{j=3}^ka_j+\ldots+b_{k-2}\prod_{k-1}^ka_j+b_{k-1}\prod_k^ka_j+b_k \end{align} $$

Let us denote the vertical vectors containing the coefficients $a_k,b_k$, as $A,B$, respectively. If we pre-fix $x_0$ to $B$ and post-fix unity (1) to $A$, then we can simplfy the above to its canonical form, namely

$$ x_k=\sum_{j=1}^k b_j \prod_j^{k+1}a_j $$

This solution has been tested against the recurrence relation for arbitrary (random) real and complex parameters and initial conditions. In addition the relation is valid for negative indices by simply mapping $A\mapsto 1/A$ and $B\mapsto -B/A$.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.