# Questions tagged [recurrence-relations]

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

6,957 questions
Filter by
Sorted by
Tagged with
21 views

### Counting with Recurrence Relations

Find the recurrence relation for a(n) - number of ternary strings of length n, containing the number 2 odd times. Some of these: 012,112,12,02,... .
56 views

### How do I solve the non-homogeneous recurrence relation $f(n) = f(n-3) +1$?

This is part of a question from my combinatorics homework I've been trying to solve for a few days now... The initial conditions are: f(0)=f(1)=f(2)=1 I tried first to solve the homogeneous part by ...
27 views

17 views

### Random walk and stationary distribution

I wonder what types of random walk have stationary distributions? I have come across random walk examples in lecture where the states are all null recurrent for dimension 2 and lower, transient in ...
21 views

### validation of third variation on Fibonacci’s rabbit sequence

Here is a third variation on Fibonacci’s rabbit sequence. We begin with one pair of newborn rabbits. Once the pair is three months old, the pair has one pair of offspring, and continues to have one ...
29 views

43 views

53 views

### Solve the following recurrence relation

Given that $$a_{n+1}=(r+1)a_n-ra_{n-1}$$ where $r$ is a known parameter, I have to find an expression for $a_n$ knowing that $a_0=0$, $a_T=1$ (where $T$ is also a known parameter).
69 views

### Recurrence relation for the partial sum of an alternating series

If $z \in \mathbb{Z}^+$ and $p_{z,n}$ is the number of sequences, $a_1, \dots, a_n$ of size $n$ where $a_i \in \mathbb{Z}^+$, so that for $0 \leq j \leq n$: $$0 \leq \sum_{i=1}^j (-1)^{i-1}a_i \leq z$$...
31 views

### Finding the general formula for the sequence with $d_0=1$, $d_1=-1$, and $d_k=4 d_{k-2}$

Suppose that we want to find a general formula for the terms of the sequence $$d_k=4 d_{k-2}, \text{ where } d_0=1 \text{ and } d_1=-1$$ I have done the following: \begin{align*}d_k=4d_{k-2}&...
20 views

### How can I find the complexity of this recurrence?

I've to solve the following recurrence: $T(n) = 2T(n-1) - 1$, for $n \geq 1$ $T(n) = 1$, for $n = 0$ I'd easily proved that $T(n) = O(2^n)$, however it seems that $T(n)$ is $O(1)$ actually. So, ...
19 views

### Recurrence equation process of solving

i am solving some reccurence relations and I am getting lost and not sure where to go I have $$T(n)=T(n-1)+ 1/7^{(n-1)}\quad \text{ where } T(1)=1$$ Which I tried solving with something like this <...
52 views

40 views

### A permutation π on $[n]$ is said to be even-dominated if $\phi_{2i−1}< \phi_{2i}> \phi_{2i+1} \ for \ all 1 ≤ i < n/2$

Let a be the number of even-dominated permutations on $[n]$. Let $a(x)$ be the exponential generating the function of $(a_n)_{n≥0}$.
44 views

### Show if $x_1=1, x_2=2, x_n=\frac{1}{2}(x_{n-1}+x_{n-2})$, then $1\le x_n \le 2$ for all $n\in\mathbb{N}$ using Strong Induction
Let $x_1=1$, $x_2=2$, and $x_n=\frac{1}{2}(x_{n-1}+x_{n-2})$. Show using strong induction that $x_n\in [1,2]$ for all natural $n$. So I know just from inequalities that if $a<b$ then \$a<\frac{...