# Questions tagged [recurrence-relations]

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

8,282 questions
Filter by
Sorted by
Tagged with
34 views

40 views

### Solving the recurrence $a^2_n – 5a^2_{n-1} + 4a^2_{n-2} = 0$, where $a_0=4$ and $a_1 = 13$ [closed]

Solve the recurrence relation $$a^2_n – 5a^2_{n-1} + 4a^2_{n-2} = 0$$ if $a_0=4$, $a_1 = 13$, $n>1$.
1 vote
39 views

### Solving the Recurrence relation of $T(n) = 2n + 2 \sum_{k=1}^{n-1} T(k)$

I want to solve $$T(n) = \begin{cases} 2n + 2\sum_{k=1}^{n-1} T(k) & n > 1 \\ 1 & n = 1 \end{cases}$$ but i got stuck at sigma notaion, if $T(n-1)$ its gonna change into $T(n-2)$, $T(n-3)$...
35 views

42 views

### Let $a_n$ be the number of $X$-strings of length $n$ that do not contain $344$ as a sub-string. Find a recurrence relation for $a_n$.

Let $X = \{1,2,3,4\}$ and $a_n$ be the number of $X$-strings of length $n$ that do not contain $344$ as a sub-string. Find a recurrence relation for $a_n$. We can construct a string of length $n$ in ...
29 views

### Third-order homogeneous linear recurrence relation with quadratic coefficients

I am looking for techniques to simplify or solve the recurrence $$\sum_{k=0}^3(a_k n^2 + b_k n + c_k) x_{n+k} = 0$$ with initial conditions $x_0,x_1,x_2$. The coefficients $a_k,b_k,c_k$ are ...
1 vote
25 views

### Akra-Bazzi method for $n^2/\log_2(n)$ driving function

I came across $T(n) = 3T(n/3)+8T(n/4)+n^2/\log_2(n)$ with driving function $f(x) = \frac{x^2}{\log_2(x)}$ in the CLRS 4th ed. textbook and am having a tough time applying the Akra-Bazzi method to it. ...
33 views

### period of recurrence relation

Find the period of the recurrence sequence with $s_{i+5} = s_{i+1} + s_i$ in $\mathbb{F}_2$ and initial states $s_0 = 1, s_1 = 1, s_2=1, s_3=0, s_4=1$. Firstly, I calculated the characteristic ...
178 views

39 views

### Second order linear recurrent sequence

Does anyone know the answer to this question regarding recurrence relations? To determine the general solution of the following recursive relation with the initial conditions. Write down the roots in ...
48 views

### Recurrence relations for even orthogonal polynomials

I have been playing around with the theory of orthogonal polynomials, and it occurred to me that we might be able to build a family of orthogonal polynomials from even powers of a variable $x$. For ...
98 views

### Consider sequence of numbers $a_r,\;r\geq0\;$ with $a_0=1\;$ and $a_{r+1}^2=1+a_r\cdot a_{r+2}.\;$ Then which of the following is/are true?

Let $\alpha, \beta$ are roots of equation $x^2-a_1 x+1=0$ and consider sequence of numbers $a_r,\;r\geq0\;$ with $a_0=1\;$ and $a_{r+1}^2=1+a_r\cdot a_{r+2}.\;$ Then which of the following is/are true?...
102 views

### Solving recurrence relation $T(n) = T(n - 1) + n^2$ using mathematical induction.

I am trying to solve a recurrence using the induction principle (I am asking for help/confirmation about this solving method, so don't answer with a solution developed by iteration method or something ...
1 vote
81 views

### How to represent this one-dimentional movement in math?

I'm struggling trying to convert this movement behavior into an equation. For future reference, this is as a result of searching for a solution for a previous question of mine. Thank you @eyeballfrog ...
34 views

I feel very strange asking this but here is a problem I have from a textbook of mine. Simply put, I do not understand how (a_(t-1)*a_(t-2)…a_1) became the pi-product of a_i/a_o. As a result, I dont ...
41 views

1 vote
27 views

### Closed form representation for $\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}k$
Answering some other question, I stumbled upon the following relationship: For $n\in\Bbb N$ let $$p_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}k$$ and let a_n = p_n+p_{n-2}\quad \text{ if } n \...