Questions tagged [recurrence-relations]

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

Filter by
Sorted by
Tagged with
5 votes
2 answers
34 views

Recursive averaging sequence

Let $x_1,x_2,x_3\in\mathbb{R}$ be three distinct real numbers. I am interested in the convergence of the sequence $$ x_{n} = \frac{x_{n-2}+x_{n-3}}{2},\quad n = 4,5,\ldots $$ ie, $$ x_{4} = \frac{x_{2}...
user avatar
-1 votes
1 answer
24 views

Tiling of a 6xn rectangle with 6x1 tiles [closed]

What would the recurrence formula for the tiling of a 6xn rectangle by 6x1 tiles be?
user avatar
0 votes
0 answers
30 views

Show that $A_{k+2} = A_k$ for some $k$

$A$ is an n-tuple of nonnegative integers $(a_1,\cdots, a_n)$ so that $a_i\leq i-1$. Given any such $n$-tuple,define the successor $A' = (b_1,\cdots, b_n)$ where $b_1=0,b_{i+1}$ is the number of ...
user avatar
0 votes
1 answer
14 views

solution for system of non homo linear recurrence relations

After finishing some BP(back propagation) problem, I ended up by these equations: $$W_1(0) = 1.5$$$$W_2(0) =0$$ $$W_1(x+1) = W_1(x) -2B(x)+\frac{W_2(x)-W_1(x)-1}{5}$$ $$W_2(x+1) = W_2(x) -2B(x) +\frac{...
user avatar
  • 1
-5 votes
0 answers
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$.
user avatar
1 vote
1 answer
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)$...
user avatar
2 votes
1 answer
35 views

Two different recurrence relations, same solution

Say, I want to solve two recurrence relations in 2D given by $$\begin{cases}\alpha_{i,j}=\frac{1}{4}\left(\alpha_{i+1,j}+\alpha_{i-1,j}+\alpha_{i,j+1}+\alpha_{i,j-1} \right)\\\alpha_{i,j}=\frac{1}{4}\...
user avatar
0 votes
0 answers
11 views

Solve the recurrence relation $f_n = af_{n-1} + (a-1)[n + (a-1)] + (a-2)$, where a is a positive integer and a>=2. [closed]

Solving a recurrence relation What type of recurrence relation is it and what is the approach?
user avatar
  • 1
9 votes
0 answers
141 views

Positive integer solutions of $ab+1=x^2, ac+1=y^2, bc+1=z^2, x+z=2y$

A question essentially the same a this one was asked in MSE 4479792 without any background details and was deleted by the post author after I posted a minimal one sentence answer mentioning five OEIS ...
user avatar
  • 29.6k
0 votes
0 answers
25 views

Characterizing this recursively defined family of polynomials

Define the set $S$ recursively as: $$\forall \>\theta_1,\theta_2 \in \mathbb{R}, \> \forall \>0\geq a \geq 1,\> (ae^{i\theta_1}, \sqrt{1-a^2}e^{i\theta_2})\in S$$ and $$\forall \>(P,Q) \...
user avatar
  • 236
0 votes
1 answer
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 ...
user avatar
  • 11.9k
0 votes
1 answer
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 ...
user avatar
  • 1,826
1 vote
0 answers
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. ...
user avatar
  • 11
0 votes
0 answers
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 ...
user avatar
11 votes
2 answers
178 views

Given a sequence with $a_1=1$ and $a_{n+1}=a_n-\frac13a_n^2$. Is there an easier way to get an upper bound of $1/a_{100}$?

Suppose that a sequence $\{a_n\}_{n=1}^\infty$ satisfies $a_1=1$ and $$a_{n+1}=a_n-\frac13a_n^2,\qquad n=1,2,3,\cdots.$$ Which of the following is true? (A) $2<100a_{100}<\frac52$ (B) $\frac52&...
user avatar
  • 6,638
1 vote
3 answers
63 views

Find expression of $c_n$, where $c_n = a_n + b_n$

Given the recurrence relation $a_{n+2} = 3a_{n+1} + 6a_n$ and $b_{n+2} = b_{n+1} + b_n$ I am supposed to find an expression of the recurrence relation for $c_n := a_n + b_n$. I tried to find some form ...
user avatar
3 votes
2 answers
91 views

sequence such that $x_{n+1}=n(x_n-n)$

Let $(x_n)$ be a sequence such that $x_{n+1}=n(x_n-n)$ Prove that $x_n=O(n)$ if and only if $x_1=2e$ If we have $x_n=O(n)$ then clearly $x_n=n+O(1)$ so they are equivalent. I don't get how $x_1$ ...
user avatar
  • 610
4 votes
1 answer
62 views

Recurrence relations with non-constant coefficients - Book Recommendations

I've recently realised that recurrence relations (difference equations) can be quite powerful, especially when you start using non-constant coefficients... Can anyone recommend any good books that go ...
user avatar
  • 131
0 votes
0 answers
49 views

Prove a Predicate is Primitive Recursive

Suppose $x$ is Godel's number of some formula. Predicate $\operatorname{P}(\operatorname{f}(x))$ is true only when the number of functions is equal to the number of predicates in that formula. Prove ...
user avatar
2 votes
2 answers
81 views

Is it possible to find the explicit formula for the recurrence relation $a_n = b_{n}a_{n-1} + a_{n-2}$, where $b_{n}$ are known?

Given $a_n = b_{n}a_{n-1} + a_{n-2}$ with starting conditions: $a_0 = 0,\ a_1 = 1$ I need the explicit form of $a_n$. $b_n$ are known. For example, let's say $[b_2,b_3,b_4,b_5] = [1,2,3,1]$. The first ...
user avatar
1 vote
2 answers
75 views

Recurrence of a state in an infinite state space for discrete markov chains

Question Let $(X_n)_{n\ge0}$ be a Markov Chain with stochastic matrix P, determine whether or not the state $0$ is recurrent when $p_1=p_2<0.5$ and $\gamma >0$. The stochastic matrix P is given ...
user avatar
  • 1,157
1 vote
0 answers
33 views

Recursive system unique solution

General question: How does one identify if a system of recursive equations (a slightly more complicated system than the standard $Ax=b$) has a unique solution? Specific example: My system of two ...
user avatar
  • 154
0 votes
1 answer
53 views

Number of labelled triangular cactus graphs

I want to count triangular cactus graphs: https://en.wikipedia.org/wiki/Cactus_graph#Triangular_cactus I belive it can be done by creating recurrence realation, and then by analyzing its generating ...
user avatar
  • 125
3 votes
3 answers
94 views

What is the general solution of the linear difference equation $y_{n+3}-4y_{n+2}+5y_{n+1}-2y_n=2^n$

What is the general solution to the linear difference equation: $$y_{n+3}-4y_{n+2}+5y_{n+1}-2y_n=2^n$$ I followed the instructions given in this video. And I got the following for the homogeneous part ...
user avatar
0 votes
0 answers
15 views

Solving difference equation with Z transform reduces solution space?

I recently learned about the Z transform and I tried solving the equation: $$(1) : x[n]-x[n-1]-x[n-2]=\delta[n-1], x: \mathbb{Z} \rightarrow \mathbb{C}$$ which has the Fibonacci sequence (with $0$ at ...
user avatar
2 votes
2 answers
140 views

How should I find $a_n$ knowing that $a_n = a_{n-1} + a_{n-3}$

I tried using a quadratic formula by using the constants of the recursive formula. Then when I get the solutions of the quadratic function, I would insert the $x$ values gotten to $a_n = a_1 \cdot (...
user avatar
  • 29
0 votes
1 answer
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 ...
user avatar
3 votes
0 answers
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 ...
user avatar
  • 195
5 votes
2 answers
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?...
user avatar
  • 2,050
0 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 58
0 votes
2 answers
34 views

How was this geometric product series simplified?

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 ...
user avatar
0 votes
1 answer
41 views

Substitution method to solve recurrences.

Apparently, I didn't fully understood the substitution method to find upper/lower bounds of a recurrence relation. I know that this method have it's basis on the induction principle. For example: $$ T(...
user avatar
0 votes
1 answer
76 views

Solving recurrence T(n) = T(n - 1) + n^2 using substitution method.

I am trying to solve a recurrence using substitution method (I am asking for help/confirmation about this solving method, so don't answer with a solution developed by iteration method or something ...
user avatar
0 votes
2 answers
50 views

How can I find an asymptotic solution to this recurrence?

How can I find an asymptotic solution to the recurrence $$T(n) = 4T(n/4) + 2T(n/2) + C$$ I replaced the $4T(n/4)$ with $4T(n/2)$ and used the master theorem to get an upper bound of $O(n^{\log_2 6})$ ...
user avatar
-1 votes
1 answer
59 views

Solving recurrence relation T(n) = T(n - 1) + 3n substitution method.

Given: $$ T(n) = \begin{cases} 4, & n = 1\\ T(n - 1) + 3n, & n > 1\\ \end{cases} $$ I was trying to prove that $T(n) = O(n^2)$ using the substitution method. I guess that the solution is $O(...
user avatar
0 votes
1 answer
43 views

Recurrence relations in dynamic programming

I have the following problem: Assume a truck collects items from a grid with n*n size starting at location (0, 0)and delivers them to a terminal (n, n). The truck can move right, left or down. There ...
user avatar
0 votes
3 answers
49 views

Solving recurrence relation T(n/2) + n substitution method

I am studying the substitution method to find the asymptotic behavior of a recurrence relation and I was trying to prove that: $$ T(n) = \begin{cases} 1, & n = 1 \\ T(\lfloor\frac{n}{2}\rfloor) + ...
user avatar
1 vote
1 answer
27 views

Is difference equation $t_n = (a+b) t_{n-1} - ab \cdot t_{n-2}$ possible ($t_1 = a + b$ and $t_2 = a^2 + ab + b^2$)?

I had problem solving difference equation $t_n = (a+b) t_{n-1} - ab \cdot t_{n-2}$ where $t_1 = a + b$ and $t_2 = a^2 + ab + b^2$. Here is what I have done: First, I've written down the equation as $$...
user avatar
  • 353
0 votes
1 answer
47 views

Is $0 \le p_n = \sum_{k=1}^n \frac{(-1)^{k+1}}{(2k)!}p_{n-k} \le 2^{-n}$ where $p_0= 1$?

Let $(p_n)_n$ be the sequence defined by $p_0 = 1$ and $$p_n = \sum_{k=1}^n \frac{(-1)^{k+1}}{(2k)!}p_{n-k}.$$ Using Python, I notice that $0 \le p_n \le \frac{1}{2^n}$. I was unable to prove it by ...
user avatar
1 vote
1 answer
54 views

Is the structure of sequence A094615 obvious?

Is the triangular structure described in A094615 proven? That is, is it proved that the following computation lasts forever? \begin{eqnarray*} 3 &=& 2\cdot 1 + 1 \\ 5 &=& 3\cdot 1 + 2 \...
user avatar
  • 426
0 votes
0 answers
18 views

Convergence and divergence behavior of recurrence relations

In our lecturer's notes which can be seen below. We have a nonconstant $b$ values while we are studying $Y_t = A * b^t - c $ kind of problems. Is it a typo where she meant to put $Y_t$ on the x-axis ...
user avatar
2 votes
1 answer
53 views

Eigenvalues for discrete second derivative with periodic boundary conditions

This wikipedia page https://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors_of_the_second_derivative for the discrete second derivative ivative says that the eigenvalue problem $v_{k+1}-2v_k+v_{k-1}...
user avatar
1 vote
1 answer
38 views

How can I prove differential recurrence relation of Legendre polynomials without generating function?

What I am trying to prove is $P'_{n+1}(x)−P'_{n−1}(x)=(2n+1)P_n(x)$ What I can use are here: $P_0(x)=1$, $P_1(x)=x$ $\int_{-1}^1 P_m(x)P_n(x) \;dx = 0 \;(n\neq m)$ (the orthogonality of Legendre ...
user avatar
1 vote
0 answers
34 views

Finding sum of coefficients of permutations of function compositions

I have a pair of functions: $$ \begin{align} g(x) &= 3 x \\ h(x) &= -4 x ^ 3 \end{align} $$ I want to compose $g$ and $h$, applying each $N_g$ and $N_h$ times, respectively. A few examples ...
user avatar
8 votes
3 answers
172 views

Every polynomial sequence satisfies a linear recurrence?

I noticed an interesting pattern, which is that the sequence $a_n = n^2$ satisfies the recurrence relation $1a_{n-3} - 3 a_{n-2} + 3 a_{n-1} - 1a_n = 0.$ This is an alternating weighted sum of 4 ...
user avatar
2 votes
1 answer
169 views

Closed / explicit form of a recursively defined real function involving a square root?

Let $x\geqslant-1$ be a real number, and $x_n$ be a sequence defined recursively as: $$x_{n+1}= \begin{cases} x_n\sqrt{\dfrac{1+x_n/x_{n-1}}2}, &\text{ if } x_n\neq 0 \\ 0, &\text{ if } x_n = ...
user avatar
2 votes
2 answers
53 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 \...
user avatar
3 votes
0 answers
144 views

Question on a recurring sequence.

Let $[n]$ denote the set of first $n$ natural numbers along with $0.$ For each $n \in \mathbb N$ define a map $p^{(n)} : [n] \times [n] \longrightarrow [0,1]$ as follows $:$ $p^{(n)} (i,j) = p^{(n)} (...
user avatar
2 votes
2 answers
87 views

Single Solution for this Recurrence: $a(n)=3^n-a(n-1)+1$

I've solved this recurrence using the iteration method for even and odd values of $n$, but I cannot seem to find a singular explicit function that solves this recurrence for all values of $n$. The ...
user avatar

1
2 3 4 5
166