6
votes
0answers
40 views

Recurrence relations with multiple roots of auxiliary equation

Suppose we have a homogeneous linear recurrence relation of the form $$u_{n+r}+a_1u_{n+r-1}+\dots +a_ru_n=0$$ The auxiliary equation is then $$f(x)=x^r+a_1x^{r-1}+\dots +a_r=0$$ It is well known that ...
1
vote
1answer
16 views

third order recurrence relation with non-constant coefficients

Does anyone know of a paper that may have been written on $3^{rd}$ order recurrence relations with polynomial coefficients, that is, one of the form $$A(n)a_{n+3}+B(n)a_{n+2}+C(n)a_{n+1}=D(n)a_n$$ ...
0
votes
1answer
45 views

General solution of a finite-difference equation with real non-commensurable differences.

How to find a general solution of the following functional (recurrence) equation: $$f(x) = c_1 f(x - a_1) + \dots + c_n f(x - a_n), \tag{1}$$ where $c_i, a_i$, $i = 1, ... n$ are arbitrary real ...
1
vote
2answers
60 views

Reference Request: Difference Equations

I am taking a second course in calculus and came across sequences defined inductively, as in recursively. My teacher told the class that a general formula for the $n$th term can be obtained using a ...
4
votes
0answers
156 views

General overview about Recursion (free online texts)

I'm looking for free online texts about recursion. What I'm looking for formal definitions* of "all" (most of) the different types of recursion and from different points of views like Category ...
2
votes
1answer
129 views

Numerical Solution of difference equation

I am trying to solve a nonlinear difference equation of the form: $x_{i+1} = f(x_i, x_{i-1})$ for $i = 0,\ldots,N-1$ with given boundary conditions $x_0 = a$ and $x_N = g(x_{N-1})$ where $f$ and $g$ ...
2
votes
1answer
145 views

Heighway dragon and twindragon relation

The Heighway dragon F is defined as the limit set for the iterated function system $\begin{cases}f_1(z)=\frac{1+i}2 z\\f_2(z)=1-\frac{1-i}2z\end{cases}\quad$ starting from the two points 0 and 1. The ...
1
vote
1answer
55 views

How to approximate a complex linear homogenous recurrence with constant coefficients with a simple one?

Is there some standard way to approximate a complex linear homogenous recurrence with constant coefficients with a simple one? For example, I might want to approximate $$ ...
1
vote
1answer
86 views

Bivariate recurrence relation

Consider the following recurrence relation: $$A(h,0)=1\\ A(h,h)=c^h\\ A(h,r)=A(h-1,r)+(c-1)\cdot A(h-1,r-1).$$ Obviously, this is just a generalization of A008949, where $c=2$. Since I'm pretty sure ...
3
votes
2answers
202 views

Recurrence relations on a continuous domain

While attempting to read Shannon's paper I came across the following (p. 3): suppose $N\colon \mathbb{R} \to \mathbb{R}$ is a function, which for some fixed (given) set of values $t_1, t_2, \dots, ...
3
votes
1answer
64 views

Is there a name for the this kind of recursive formula?

$a_{-i}=0$ for all positive i. We have the recurrence $$ a_n = \sum_{i=1}^\infty b_ia_{n-m_i} $$ Where $m_i>0$ for all $i$.
3
votes
2answers
320 views

How to solve recurrence relations with emphasis on algorithmic complexity

I am having trouble solving recurrence relations, probably because I am missing the basics. Is there any web reference/book I can read to help me cover the basics? I watched some lectures and read ...
3
votes
1answer
509 views

How to solve recurrence relations by the generalized hypergeometric series

I am reading methods of solving recurrence relation on Wikipedia. There is one method: Many linear homogeneous recurrence relations may be solved by means of the generalized hypergeometric ...
5
votes
3answers
940 views

How to solve this recurrence relation

What are some ways to solve this recurrence relation: $a(n+1)=2 a(n) - a(n-1) -1, \text{ with }a(0)=0, a(10)=0?$ I tried to first convert this inhomogeneous equation into a homogeneous one following ...
5
votes
2answers
1k views

Second order homogeneous linear difference equation with variable coefficients

I was wondering if you would point me to a book where the theory of second order homogeneous linear difference equation with variable coefficients is discussed. I am having difficulties in getting ...