Skip to main content

Questions tagged [recurrence-relations]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
43 views

How to solve the recurrence relation $a_n=\sqrt{a_{n-2}}$

I don't exactly remember where I got this from or when, but I remember seeing this recurrence relation in a Youtube video that was just going over the different types of recurrence relations. I have ...
CrSb0001's user avatar
  • 2,534
0 votes
0 answers
15 views

Non-homogeneous, non-linear recurrence relation simplification ft. Coefficients of power series

Consider an arbitrary sequence $b_p$ such that $(-1)^{b_p} \in \mathbb{R}$. We know ,$$-1 = e^{i \pi} = \sum_{k=0}^{\infty} \frac{i^k {\pi}^k}{k!}$$ Exponentiating both sides to the power of $b_p$, $$(...
Kraken's user avatar
  • 17
1 vote
1 answer
25 views

Find the recurrence relation to find the count of n-digit numbers such that no 3 consecutive digits are same

[I am a beginner in this topic, and this is the question I have been trying to solve, which is: Let T(n) be the count of n-digit numbers (using digits 0, 1, . . . ,9, with first digit non-zero) such ...
BakaKazuya's user avatar
1 vote
0 answers
33 views

If I do random walks on recurrence relations over $\mathbb F_2$, what do I get? Some kind of discrete version of stochastic calculus?

Context: The other day I investigated a special case of recurrence relations that was an iterated running xor on bit streams which I had tried connecting to differential operators and differential ...
mathreadler's user avatar
  • 25.9k
1 vote
1 answer
71 views

A question about Chebyshev polynomials $T_n(x)$, $U_n(x)$, recurrence relations, and power of two $2^n$

I'm interested by the Chebyshev polynomials of the first kind $T_n(x)$ and of the second kind $U_n(x)$, especially $T_n(17)$ and $U_n(17)$. The recurrence relation of $T_n(17)$ can be written as $a_{n}...
Aurel-BG's user avatar
  • 131
-2 votes
0 answers
19 views

Frobenius Method: Solve $(x^ 2 +2)y ′′+xy ′−(1+xy)=0$ [closed]

So I had this Question given on an assignment but when I tried solving it, I saw that it had a lot of issues which mainly originated from that $-(1+xy)$ term as I couldn't verify what type of singular ...
Abhishek Pattnaik's user avatar
2 votes
0 answers
111 views

Is there a sequence of non-trivial continuous functions $f_{n+1}(f_{n+1}(x))=f_{n}(x)$, $f_2(x)= \frac{1-x}{1+x}$?

Just for curiosity I was trying to find a sequence of non-trivial continuous functions at $\mathbb{R}$ except finite many points such that $f_{n+1}(f_{n+1}(x))=f_{n}(x)$, $f_1(x)=x$ and by non trivial ...
pie's user avatar
  • 4,514
0 votes
0 answers
47 views

Need to find closed form of recurrence relation [closed]

I am asked to solve the following problem. Find the closed form of the recurrence relation: $a_n = a_{n-1} - a_{n-2} + a_{n-3} + 4n - 6 $ with the initial values: $a_1 = 1, a_2 = 4, a_3 = 9$ Im ...
Monk's user avatar
  • 19
5 votes
2 answers
111 views

How to evaluate$\lim\limits_{n\to\infty}n\left(n\left(n..\left(\int_0^1\left(\frac{\sqrt[n]{x}+1}{2}\right)^ndx-l_0\right)-l_1..\right)-l_{m}\right)$?

$$\lim_{n \to \infty} \int_0^1 \left( \frac{\sqrt[n]{x}+1}{2} \right)^n dx= \frac{2}{3}$$ I became curious what happens If we do the following: $$\lim_{n \to \infty} n\left(\int_0^1 \left( \frac{\...
pie's user avatar
  • 4,514
5 votes
1 answer
158 views

Consider the following recurrence, $a_n=\frac{4a_{n-1}^3+2a_{n-1}-a_{n-2}}{1+4a_{n-1}a_{n-2}}$ where $a_0=0, a_1=1$. Show every $a_n$ is an integer.

Consider the following recurrence, $$a_n=\frac{4a_{n-1}^3+2a_{n-1}-a_{n-2}}{1+4a_{n-1}a_{n-2}}$$ where $a_0=0, a_1=1$. (a) Show that every $a_n$ is an integer. (b) Find the general term of $a_n$. What ...
user526256's user avatar
4 votes
3 answers
158 views

Consider the following recurrence, $a_n = \frac{1}{2}a_{n-1}+1$ where $a_1 = 1$. Guess a pattern for $a_n$ and prove it by induction. [duplicate]

Consider the following recurrence, $$a_n = \frac{1}{2}a_{n-1}+1$$ where $a_1 = 1$. (a) Guess a pattern for $a_n$ and prove it by induction. (b) Convert the recurrence for $a_n$ into the form $a_n = ...
Logan's user avatar
  • 41
0 votes
2 answers
46 views

Why does this generating function not work - where is the mistake?

I have to solve the recurrent equation: $a_0 = 0, a_1 = 1, a_{n+2} - a_{n+1} + a_n = 0$ My approach is quite normal. So let $A(x) = a_0+a_1x+...$ be the generating function and $Q(x) = 1-x+x^2$ be ...
kamil7430's user avatar
0 votes
0 answers
42 views

Solutions for a Recurrence Relation: $a_n = -3a_{n-1} + 4a_{n-2}$

Question: Which of the following is a solution of the recurrence relation $a_n = -3a_{n-1} + 4a_{n-2}$? a. 2 b. 3 c. -1 d. 1 Attempt: I have done the following calculations and arrived at this ...
Ameer786's user avatar
  • 642
1 vote
0 answers
15 views

Looking for a solution to a 2-dimensional recurrence relation with a floor function in GF(2)

I have a recurrence relation that i'd like to solve. It is defined as follows: $$ a_{i,j} = (a_{i-1,j} + \lfloor 3 \sum_{k=0}^{j-1} \frac{a_{i-1,k}}{2^{j-k}} \rfloor \space) \bmod 2 $$ where $ a_{i,...
BlueLisztmaths's user avatar
3 votes
2 answers
136 views

Prove that if $\forall n\in\Bbb N\quad a_{n+1}^2-a_{n+1}=a_n\in\Bbb Q$, then the sequence is constant

This question was posted, downvoted and closed today (2022 Thailand Olympiad problem) and 8 days ago ($f(x+1)^{2} - f(x+1) = f(x)$. What values of $f(1)$ allow $f(x)$ to be always rational if $x$ is ...
Anne Bauval's user avatar
  • 35.8k
0 votes
0 answers
39 views

Recurrence relation for integer sequences raised to the power of $n$

An interesting pattern can be observed when considering a sequence of positive integers raised to some power $n$. When a sequence of continuous integers $i$ (of length >=n) is raised to the power ...
Edison Medison's user avatar
13 votes
1 answer
256 views

At every step, add $k$ previous terms, then remove all zeros. Then $k=3$ leads to a $300,056,874$-cycle.

Recently, I've been interested with the sequence of the form: $$a_n =\text{Zr}(\sum_{j=1}^k a_{n-j}),\ \ n≥k$$ $$a_n=1,\ \ 0≤n<k$$ Where $\text{Zr}(x)$ is just $x$ with $0$ removed in its digits (i....
Bryle Morga's user avatar
3 votes
0 answers
120 views

Solving recurrence relation to find a generating function

Say I have the recurrence: $a_t(u,v) = (a_t(u-1,v-1) + a_t(u-1,v)) q^{u-2v+t}$ with initial values: $a_t(u,v) = 0$ for $u < 0 $ , $v < 0 $, or $v > L$. Where $ L = \lfloor(u-t-1)/2\rfloor $ ...
John_R's user avatar
  • 51
3 votes
1 answer
101 views

Sequences of the form $A(n) = A(A(n-1)\bmod n)^2$

$$A(0)= x \in\mathbb{Z}^+,\ A(n) = A(A(n-1) \bmod n)^2$$ At first glance, one would think that such sequence would grow very fast. But my testing suggest that this sequence actually ends with $x^4$ ...
Bryle Morga's user avatar
0 votes
0 answers
47 views

find the coefficient $a_n$ of a power series

I have the power series $$ f(z)=\frac{2}{(1-3z)^{\frac{2}{3}}}+e^{\frac{1}{2}z^2}, $$ and I am supposed to find an explicit expression for the coefficient of the corresponding sum representation of ...
macman's user avatar
  • 37
2 votes
1 answer
89 views

A generalisation of $\lim\limits_{x\to0}\frac{e-(x+1)^{\frac{1}{x}} }{x}$.

I saw this problem:- $$\lim\limits_{x\to0}\frac{e-(x+1)^{\frac{1}{x}} }{x}.$$ Which can be easily done with l'hopital's rule. Here I wonder what happen if I did the following: Let $f_0(x):= (x+1)^{\...
pie's user avatar
  • 4,514
-1 votes
1 answer
56 views

Solving the recurrence $a_{n}=3a_{n-1}-2a_{n-2}+1$ [duplicate]

can you help me to find some solution? $$a_{n}=3a_{n-1}-2a_{n-2}+1$$ I did it like this: $$a_{n}-3a_{n-1}+2a_{n-2}=0$$ then $$a_{n}=c_{1}\cdot 2^{n}+c_{2}$$ But then I'm not able to find solution ...
baranovak's user avatar
1 vote
1 answer
124 views

Finding a closed form for the $n$-th term of the recurrence with $a_1=2$ and $a_{n}=\frac{2na_{n-1}+4n-4}{a_{n-1}+2n-2}$

Suppose $$a_{n}=\frac{2na_{n-1}+4n-4}{a_{n-1}+2n-2}$$ with $a_1=2$. How can I figure out an expression for $a_n$ in terms of $n$? This recurrence relation is from this question: There is $n\times n$ ...
applebanana's user avatar
0 votes
0 answers
21 views

Further explain natural language explanation for statements deduced from master theorem for solving recurrences

This content is taken from from Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, The MIT Press, 2022, Chapter 4. Given the following recurrence ...
jam's user avatar
  • 51
0 votes
0 answers
27 views

Reference/Textbook for Nonautonomous discrete dynamical systems

I am interested in a nonautonomous discrete dynamical system where the next value $\mathbf{x}_{t+1}$ is determined by the current value $\mathbf{x}_{t}$ and the current time $t$. However, I could not ...
HapppyJamJam's user avatar
0 votes
2 answers
44 views

Try to understand a "simple" recurrence relation...

There is this problem from AoPS: Let $n$ be a positive integer and let $a_{n}$ denote the number of positive integers which can be formed whose digits are chosen from 1,3,4 and the sum of whose digits ...
Shine's user avatar
  • 137
2 votes
0 answers
25 views

How to find tight asymptotics of a function defined in terms of a strange recurrence?

Consider the following interesting recurrence $$ \begin{aligned} Q_0(k) &= k + 1 \\ Q_i(k) &= k^{2^i} + \prod_{j = 0}^{i - 1} Q_j(k), \end{aligned} $$ and use it to define $$A(k) = \frac{1}{k} ...
crb233's user avatar
  • 1,022
1 vote
1 answer
40 views

Solve for h given $\left(\frac{2}{3}\right)^h \cdot n < n_0 \leq \left(\frac{2}{3}\right)^{h-1} \cdot n$

The recursion tree generated from the following recurrence relation $$ T(n) = T\left(\frac{n}{3}\right) + T\left(\frac{2n}{3}\right) + \Phi(n) $$ has, for some $n \geq n_0$, a depth $h$ given as a ...
jam's user avatar
  • 51
2 votes
0 answers
65 views

What is the expected maximum location reached in a $1$ dimensional random walk?

Consider a random walk in $1$ dimension starting at the location $x=0$. In each time step, the walker moves left $1$ position with probability $(1-p)$ and right $1$ position with probability $p$. ...
Patrick Gambill's user avatar
0 votes
1 answer
46 views

Difference equations applied to Random Walk

A random walk S with absorbing barriers at $0$ and $N$, at each step the particle can move right,left or stay put with probabilities (p+q+r=1). Let $W$ be the event that the particle is absorbed at $0$...
Bazman's user avatar
  • 901
0 votes
1 answer
58 views

Is this sequence always eventually periodic regardless of starting value?

$$a(n)=a(\lceil \mathop{\rm abs}(a(n-1)) \rceil\bmod n)) + a(\lceil \mathop{\rm abs}(a(n-2)) \rceil\bmod n))$$ For starting values, $a(0)=a(1)=1$, the sequence has a cycle starting with $n=441329$ ...
Bryle Morga's user avatar
3 votes
1 answer
148 views

Prove that $\displaystyle (r+1) \cdot a_{r+1} = (n-r) \cdot a_{r} + (2n+1-r) \cdot a_{r-1}$

Let $\displaystyle (1+x+x^2)^n = \sum_{i=0}^{2n} a_i x^i$. Then prove that $\displaystyle (r+1) \cdot a_{r+1} = (n-r) \cdot a_{r} + (2n+1-r) \cdot a_{r-1}$ What I try : $\displaystyle (1+x+x^2)^n=\...
jacky's user avatar
  • 5,159
0 votes
0 answers
18 views

Recurrence relation with kernel convolution

I am interested in understanding whether anything is known about recurrence relations between functions defined via convolution with a fixed kernel and with given initial conditions, namely $$M_{k+1}(...
Bright-White-Light's user avatar
4 votes
0 answers
99 views

Is this recursive function always surjective? [closed]

Let $S:\mathbb{N}\to\mathbb{Z}^+$ satisfy $$ \left\{ \begin{aligned} S(n) &= S(A^n \bmod n) + S(B^n \bmod n) \\ S(0) &= 1 \end{aligned} \right. $$ My question is, is this function always ...
Bryle Morga's user avatar
0 votes
3 answers
81 views

Closed form expressions for $T_n$ and $S_n$ of a Fibonacci-like sequence

I am a student curious about recurrence relations who has just bumped into the Intermediate 1st year (grade 11). I derived the closed form expressions for the $n^{th}$ term and the sum of $n$ terms of ...
Yatharth Shrivastava's user avatar
1 vote
1 answer
50 views

Solve the following recurrence relation: $f(N,d) = p*f(N-1,d-1) + (1-p)*f(N-1,d+1)$ subject to constraints in the body.

The constraints are $f(0,0)=1, f(0,k)=0\space \forall k \neq 0, f(N,k)=0 \space \forall k>N\space0\leq p\leq 1$ . When working on a probability problem, I came across this recursion when working ...
Patrick Gambill's user avatar
0 votes
0 answers
29 views

Explict computation of the finite product of matrices

For $n \in \mathbb{N}$ a given dimension and $m \geq 1$, consider the lower triangular matrix $A(m)\in \mathbb{R}_+^{n\times n}$ defined by $$A_{i,j}(m) := \dfrac{1}{m+i}\dfrac{1}{m-1+i} \quad \text{ ...
mathematurgist's user avatar
0 votes
0 answers
22 views

Recurrence problem about planes [duplicate]

Find the recurrence relation satisfied by Sn, where Sn is the number of regions into which three dimensional space is divided by n planes if every three of the planes meet in one point, but no four of ...
Andii Koo's user avatar
5 votes
1 answer
195 views

Shuffled image of set

A permutation $\psi: S \rightarrow S$, where $S = \{1,2,\dots,n\}$, is considered $\textit{descriptive}$ if for every $k < n$, the image under $\psi$ of $\{1,2,\dots,k\}$ is not simply $\{1,2,\dots,...
BlizzardWalker's user avatar
0 votes
0 answers
27 views

Symmetry of King's dream fractal (orbit of a 2-dimensional iterated function system is a parallelogram?)

For fixed real numbers $a,b,c,d$ define the map $f : \mathbb{R}^2 \to \mathbb{R}^2$ by $$f : (x, y) \longmapsto (\phi(ax) + b \cdot \phi(ay),\hspace{1em} \phi(cx) + d \cdot \...
Watson's user avatar
  • 23.8k
2 votes
1 answer
180 views

Property of $a_{n+1} = a_n - \frac{1}{a_n}$

For a $a_n$ defined recursively by $a_{n+1} = a_n - \frac{1}{a_n}$,$a_0 = k >0$. Prove that if the first $n$ such that $a_n \leq 0$, then $n \in O(k^2)$. I ran a computer simulation, and it seems ...
tovdan's user avatar
  • 53
2 votes
1 answer
48 views

Compute the correction of a Chebyshev approximation using the Clenshaw summation formula

Assume you have a Chebyshev approximation of a function $f(x)$ evaluated using the Clenshaw summation method, up to polynomial order $N$: $$ f(x) = \sum_{k=0}^{N-1} a_k T_k(x) = (a_0 - y_2)T_0(x) + ...
LladOS's user avatar
  • 21
1 vote
2 answers
49 views

Recurrence relationship where the difference of two consecutive terms is polynomial. Solution by generating functions.

I have this recurrence relation $$h_{n} = h_{n-1} + 4n(n-1) \ \text{for} \ n \geq 1 \ \text{with} \ h_{0} = 0, h_{1} = 0$$ I am asked to find $h_{9}$. I have attempted to solve this by generating ...
user438409385's user avatar
-3 votes
2 answers
137 views

For each postive integer $n:$ $a_n=\frac{n^2}{n^2-45n+675}.$ Evaluate $a_1+2a_2+3a_3+\cdots+44a_{44}$ [closed]

For each postive integer $n:$ $a_n=\frac{n^2}{n^2-45n+675}.$ Evaluate $a_1+2a_2+3a_3+\cdots+44a_{44}$ What I have tried: I have taken $a_1,a_2,\cdots,a_{44}$ and put these values into $a_1+2a_2+3a_3+\...
Debrogli's user avatar
  • 338
2 votes
1 answer
49 views

How to solve the recurrence relation $T(n) = T(n - log(n)) + cn$

This recurrence relation $$ T(n) = T(n - \log(n))+cn $$ is one I came up with from a computer science problem I was studying, but I'm not sure what a closed form or precise time complexity would be. ...
e13's user avatar
  • 23
2 votes
0 answers
41 views

Understand how to solve recurrence relation

Ravi Pradeep's solution uses a recurrence relation, I am new to recurrence relations but would like to understand this part of the answer. Expected Number of Coin Tosses to Get Five Consecutive Heads ...
Bazman's user avatar
  • 901
0 votes
0 answers
18 views

Recurrence formula for the moments of a half-gaussian distribution (on R+)

I am trying to compute an integral that looks like the moments of a Gaussian $\mathcal{N}(\mu, \sigma^2)$, but the main difference is that we only integrate over R+ and not R. I believe we could call ...
Julia Linhart's user avatar
0 votes
0 answers
29 views

How to find asymptotic bound for $ T(n) = n + \sum_{i=1}^{\lceil \log_3 n \rceil} T(\lfloor \frac {n}{3^i} \rfloor), n\ge 1 $?

I am solving the recurrence relation: $$ T(n) = n + \sum_{i=1}^{\lfloor \log_3 n \rfloor} T(\lfloor \frac {n}{3^i} \rfloor), $$ It looks that T(n) at every level is being divided by 3 and the depth of ...
bipvan's user avatar
  • 21
1 vote
1 answer
81 views

How to solve a recurrence relation with full history $ T(n) = n + \sum_{i=1}^{n-1} \frac{2T(i)}{3i}$?

I have to solve a recurrence relation with full history given as: $$ T(n) = n + \sum_{i=1}^{n-1} \frac{2T(i)}{3i} \tag{1}$$ I tried to solve it using the method given here and here and expanded it ...
bipvan's user avatar
  • 21
0 votes
1 answer
96 views

Generating Functions for Recursive String Compositions with Parenthetical Constraints

Consider $S$ the following recursively defined set; $S$ contains the empty string and, for any strings $a$ and $b$ in $S$, the string $(a b)$ is also in $S$. Here are the first few elements of $S$ : $$...
Allison's user avatar
  • 185

1
2 3 4 5
181