Tagged Questions

Questions regarding functions defined recursively, such as the Fibonacci sequence.

50 views

Showing that the sequence $x_n = \frac {1}{1 + x_{n-1}}$ is convergent

Sequence is recursively defined by $x_0 = 1$ I managed to show it is boundness by showing that $0 \lt x_n \lt 1$ Now, when i try to show monotony of the sequence i got the problem because ...
45 views

15 views

Recurrence $x_{k+1} = \sum_{i=1}^m \theta_i x_{k+1-i} + r_{k+1}$ solution

Let $x_k$ be the solution of the recurrence equation $$x_{k+1} = \sum_{i=1}^m \theta_i x_{k+1-i} + r_{k+1}$$ where $(r_k)$ is a general sequence. I'm trying to find a explicit solution for $(x_k)$ ...
65 views

Closed form of $a_n = 1 - \frac{a_{n-1} a_{n-2}}{4}$

Given the sequence $a_1 = 1$ and $a_2 = 1$ with: $a_n = 1 - \frac{a_{n-1} a_{n-2}}{4}$ Does there exist a closed form computing $a_n$ ? At the moment I have a problem getting a grip on the series:...
41 views

How to solve the recurrence relation $T(n)=aT(n-1)+bn^c$ with $T(1)=1$

How to solve this recurrence relation? $T(n)=aT(n-1)+bn^c \\T(1)=1,$ where a, b, c are constant. I want to solve it using generating function, but get stuck. Could anybody help me?
14 views

77 views

General solution for the series $a_n = \sqrt{(a_{n-1} \cdot a_{n-2})}$

Hey I'm searching a general solution for this recursive series: $a_n = \sqrt{(a_{n-1}\cdot a_{n-2})}$ $\forall n \geq 2$ $a_0 = 1$, $a_1 = 2$
34 views

System of linear recurrences

During some computations I came up with the following system of linear recurrences: $$B_{n+2} = 3B_n + A_n \\ A_n = A_{n-1} + B_{n-1}$$ Here I am trying to find the solution for $B$ (hoping to get ...
42 views

Making an infinite generating function a finite one

If we have some generating function $G(x)$ that generates terms indefinitely, is there a way to translate it to be a finite generating function? For example if I only want to generate the first $k$ ...
17 views

32 views

Compressing two recurrences

I have two recurrences $a_n = 9a_{n-1} + b_{n-1}$ $b_n = 9b_{n-1} + a_{n-1}$ Is there a way to combine these two so it's only in terms of $a_n$? $a_1 = 9, b_1 = 1$, if this information is needed.
In practice, do you do some work on the inductive step and then reverse your steps? For example. Say you have this recurrence: $f(n+1) = 2f(n) + 1$ with $f(0) = 0$ This creates the sequence \$0, 1, ...