Questions tagged [recurrence-relations]

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

Filter by
Sorted by
Tagged with
0
votes
2answers
39 views

How to find a non-recursive formula for a recursively defined sequence

Given: $\mu(0)=0$ $\mu(i)= 2\mu(i-1) + 2^{i-1} \ \ \ \ \ \ \forall i \in N $ I would like to know if there is any way of obtaining the non recursive formula for $\mu (i)$: $\mu(i) = i2^{i-1}$ ...
0
votes
2answers
31 views

calculating total number of allowable paths

I seem to be struggling with the following type of path questions Consider paths starting at $(0, 0)$ with allowable steps (i) from $(x,y)$ to $(x+1,y+2)$, (ii) from $(x,y)$ to $(x+2,y+1)$, (iii)...
-5
votes
0answers
55 views

Rumor has it in Canada that needs to be solved… [closed]

A rumour is being spread by students in Canada. At the start of day $1$, a set of $10$ people know the rumour. Let $S_0$ be this set of people, and for $n \geq 1$, let $S_n$ denote the set of people ...
0
votes
2answers
22 views

finding formula for generating function for recurrence relation

I need to solve the recurrence relation $$A_n=2A_{n-1}+A_{n-2}$$ with $A(t)=\sum_{n=0}^\infty A_n t^n$ and initial conditions $A_0 = 1$ and $A_1=2$. I am trying to find the generating function ...
1
vote
0answers
18 views

Solving recurence equations - reference request

I have to solve several recurrence equations originating from physical problems, and I am looking for some references where techniques for different types of equations are collected. Most of my ...
0
votes
3answers
22 views

Trial solution for in-homogenous differential equation with complex numbers

I am trying to solve following: Given is the differential equation $y^{(4)} + 4y'' + 16y = b(x)$ with the solutions $z_{1,2}=±2i$. Now I have to find trial solutions for the particular solutions, ...
2
votes
2answers
34 views

Closed form of a specific recurrence relation

I have the following equation which I am trying to find the closed form for: $$ x_{n+1} = \frac{1}{2}-\frac{x_{n}}{2}$$ So far rearranging and substituting has yielded the following equations: $$...
2
votes
1answer
25 views

Recurrence relation of Sn that depends on Sn-1

OK, so I have run into this weird question about recurrence relations that I cannot complete by myself (first year comp. sci. student and first discrete math class, studying by myself). To help you ...
1
vote
3answers
122 views

Recurrence relation with python. [closed]

How to find the terminating value of the continued fractions $$ S=3-\cfrac2{3-\cfrac2{3-\cfrac2{\ddots}}} $$ by writing a recurrence relation in Python? (Start from any guess value other than 1.)
1
vote
1answer
53 views

Prove a number doesn't belong to a sequence

You are given the sequence defined by the following recurrence relation: $$a_n = \cases{a_0 = 1\\a_1 = 3\\a_{n+1} = 5a_n + a_{n-1}, \forall n \geq 1}$$ You are then asked to prove that $123456789 \...
0
votes
0answers
21 views

Steady state of a non-trivial Markov chain.

This is a generalization of the question Solving another non-trivial recurrence relation. Let $\lambda^C \ge 0$, $\lambda^M \ge 0$ and $\Lambda \ge 0$ and $q\in (0,1)$..Without loss of generality we ...
-2
votes
0answers
14 views

Relation Recurrence

Problem: d. Solution Where are they getting the constant factor 2 from? Solution
0
votes
2answers
15 views

Finding a particular solution of a recurrence relation

Consider the following recurrence relation $$X_{n+1} - \rho X_n = W_{n+1}, \ \ \ \ \ \ \ \ \ \ \ n\geq 0$$ with initial condition $X_0 = Y$ and $\rho \in (0,1)$. I would like to find a particular ...
1
vote
2answers
28 views

Prove that $X_n=(-5)^nX_0+a_n$ where $a_n=-5a_{n-1}+\frac{1}{n}, a_0=0$

Let $X_n=-5X_{n-1}+\frac{1}{n}$ for some initial value $X_0$. Prove that $X_n=(-5)^nX_0+a_n$ where $a_n=-5a_{n-1}+\frac{1}{n}, a_0=0$. Determine the condition of the calculation task $ X_{20} $ due to ...
3
votes
1answer
28 views

Prove $a_t \leq \frac{c}{t}$

We have the recursive equation $$a_t^2 = (1 - a_t)a_{t-1}^2$$ $$a_0 = 1$$ Prove that there exists constant $c$ such that $a_t \leq \frac{c}{t}$, and find the smallest such $c$. I was able to get ...
0
votes
0answers
19 views

Given this recursive sequence, how do I find the general term? [closed]

The sequence is: $$a_1 = 3$$ $$a_{n+1} = \frac{1}{2}(3a_n^2 +1) - a_n, \;n \geq 1$$ How do you find the general term of this sequence?
1
vote
2answers
29 views

How to transform a m-th order difference equation into a first order system of difference equations?

I have a problem that asks for following: Consider the in-homogenous linear difference equation $y_t-4y_t+2y_{t-3}=4^t$. Write the LDE as a system of first-order LDEs. The solution is given: define $...
-3
votes
0answers
39 views

Detailed steps for Zeilberger's creative telescoping for hypergeometric sums?, exactly after specifying $r(n)$ and$p(n)$ using Gosper's algorithm.

I would like to begin by apologizing because I am short of application on how to apply the algorithm on finite sums. my questions are maybe like the following: 1. how to check that our sum is ...
0
votes
1answer
31 views

Finding an explicit formula for the following exponential generating function [duplicate]

So I have the following formula for the coefficient of the recursion and I am trying to find an explicit formula for $a_n$ the nth coefficient: $$ a_n = (n+1)a_{n-1} + 3^n $$ $$ a_0 = 1; \space\...
-1
votes
0answers
26 views

Prove that in a recurrence relation a_n+2 = a_n+1 + a_n , m | n if and only if a_m | a_n [closed]

I came up with this problem in a Problem Set on Recurrence Relations : Prove that in a recurrence relation a_n+2 = a_n+1 + a-n , m |n if and only if a_m | a_n I can understand this is a fibonacci ...
0
votes
1answer
18 views

Validity of Proof that Recursive Function is Increasing

I have a recursive function defined as follows, $$a_{1}=1,a_{k+1}=\sqrt{2a_{k}+3} \: \forall k\in \mathbb{N}$$ I think I found a very quick way to demonstrate that the function is increasing, but ...
4
votes
1answer
70 views

Convergence of a recurrent sequence

Sorry if this was already proved (that sequence converges to $\pi$) but I cannot find that proof. So recurrent sequence is : $$a_{n+1}=a_{n}+\sin(a_n)$$ and it seems if $0 < a_0 < 2\pi$ it ...
-4
votes
0answers
33 views

For constants $a$ and $b$, the general solution of the recurrence relation $a_n = 4a_{n-1}+12a_{n-2}$ is…? [closed]

For constants $a$ and $b$, the general solution of the recurrence relation $$a_n = 4a_{n-1}+12a_{n-2}$$ is...?
0
votes
1answer
15 views

Reference stability/convergence of nonlinear recurrence relations using analytical methods

Example of a problem Let’s say we have the recurrence relation : $$ x_{n+1}=\frac{2}{3}(2x_n -x_n^2). $$ We can easily find its fixed points, namely $x=0$ and $x=1/2$. I have found numerically that ...
1
vote
1answer
11 views

Limit of Recursive Function (Methodology)

Goal: Find $$\lim_{n \rightarrow \infty} d_{n+1}^2$$ where $$d_{n+1}^2 = d_n^2 + r^2 - 2 \cdot r \cdot d_n \cdot \cos \theta$$ for constant $r$ and $\theta < \frac{\pi}{2}$. Attempt: \begin{...
0
votes
0answers
33 views

Recurrence relation proof

Let $\alpha$ be a positive integer. Let $b_n$, $n=1, 2, 3 \ldots$ be the sequence given by the recurrence relation $b_{n+2}=2\alpha^2b_{n+1}-\alpha^4 b_{n}$, $n=1, 2, 3 \ldots$ with initial ...
4
votes
2answers
63 views

solution to recurrence relation $ a_{n+2}=-2 a_{n+1}+8 a_n+4n^2$

Find the solution for the below recurrence relation with initial conditions $a_1=10$, $a_2=31$ $$ a_{n+2}=-2 a_{n+1}+8 a_n+4n^2\,. $$ Let us first consider the corresponding homogeneous recurrence ...
0
votes
0answers
12 views

Question about Expected Values for a probabilistic recurrence relation

Let $Q(x)$ be such that $$Q(x) = \begin{cases} Q(x - 1) + 1 & \text{w.p.} \ \ 0.5 \\ 0.5Q(x - 1) & \text{w.p.} \ \ 0.5 \\ \end{cases}$$ with $Q(1) = 1$. What is the expected value of $Q(n)$ ...
0
votes
1answer
20 views

Searching for a linear operator specified as a recurrent relation

I am learning about operators and some other stuff in linear algebra, and I have never encountered a problem that involves a linear operator which is defined recursively, that is: $$A: V \to V$$ $$A ...
0
votes
1answer
34 views

Markov chain recurrence solving

I am given a transition matrix for the markov chain on the space state $X=\{1,2\}$ $P=\begin{pmatrix} 1-a & a\\ b & 1-b \end{pmatrix}$ We are asked to find $P^n$ as a hint I am told to notice ...
0
votes
0answers
29 views

Can a closed form for the following recurrence relation be found?

I stumbled across a problem that involves the following recurrence relation (also with different values for the $\frac{2}{3}$): $$ p(x+1) = p(x) + \frac{2} {3p(x)}\\ \text {or in alternate form}\\ p(...
0
votes
1answer
27 views

Generating Function of Integer Partitions

Let $p_{k}(n)$ be a number of partitions of $n$ that into parts not greater than $k$. $p_{k}(n)=p_{k-1}(n)+p_{k}(n-k)$ i will prove this partition recurrence bu using Generating Functions of ...
0
votes
2answers
26 views

How to solve linear recurrence relation based on conditions?

Given $F(n)=a\cdot F(n-1)-b$ ,$n$ even $F(n)=a\cdot F(n-1)+b$ ,$n$ odd $F(0),a,b$ are constants. How to calculate $n$-th term in $log(n)$ time? I learnt matrix exponentiation technique. But ...
0
votes
0answers
36 views

Prove $\left(m-2\right){2m-3\brace m-1}>m{2m-3\brace m}$

How it can be shown that: $$\left(m-2\right){2m-3\brace m-1}>m{2m-3\brace m}$$ For $ m>2$. Where ${n\brace m}$ denotes Stirling numbers of the second kind. Using the recurrence ${n\brace m}={...
0
votes
1answer
28 views

Confusion about one of the conditions for the Akra-Bazzi method solving recurrences

In this paper by Akra & Bazzi, we consider linear divide-and-conquer recurrences of the form: $$u_n = \begin{cases} u_0 & n = 0 \\ \sum_{i=1}^{k} a_{i} u_{\lfloor \frac{n}{b_{i}} \rfloor} + ...
1
vote
1answer
38 views

Derivative of exponential with function argument

I am trying to derive an expression for the derivative of an exponential. Here is the task phrased as a problem For the function $g(x) = \exp(f(x))$ where $f(x)$ is real valued and continuously ...
35
votes
0answers
2k views

Is OEIS A248049 an integer sequence?

The OEIS sequence A248049 defined by $$ a_n \!=\! (a_{n-1}\!+\!a_{n-2})(a_{n-2}\!+\!a_{n-3})/a_{n-4} \;\text{ with }\; a_0\!=\!2, a_1\!=\!a_2\!=\!a_3\!=\!1.$$ is apparently an integer sequence but I ...
1
vote
1answer
27 views

Solution to Second Order Difference Equation for PDEs

I am using the book by Strauss on partial differential equations and I am looking at the proof for stability requirements of numerical approximations. There is a part of the proof that I don't quite ...
2
votes
1answer
119 views

Given two functions with recurrence relations and starting values, prove that $f(2020)<5$

There are two functions $f:\mathbb N\to \mathbb R^+$ and $g:\mathbb N\to \mathbb R^+$. For all $n\in \mathbb N$: $$f(1)=1$$ $$g(1)=2$$ $$f(n+1)=\frac{1+f(n)+f(n)g(n)}{g(n)}$$$$g(n+1)=\frac{1+g(n)+f(n)...
3
votes
1answer
68 views

A question about the plastic number

The plastic number is well known to be the limiting ratio of the Padovan sequence (OEIS A000931), to wit, $$ P_n=P_{n-2}+P_{n-3}\\ \lim_{n\to \infty} \frac{P_{n+1}}{P_n}=p $$ However, it is also the ...
1
vote
2answers
78 views

Given the sequence $a_{n+1}^3 = a_n^2 a_{n-1}$, with $a_0=1$ and $a_1=a$ find $a$ such that $\lim\limits_{n \to \infty} a_n = 8$.

Consider the following sequence $(a_n)_{n \ge 0}$ (it has positive terms): $$a_0 = 1$$ $$a_1 = a$$ $$\hspace{3.5cm} a_{n+1}^3 = a_n^2 a_{n-1} \hspace{2cm} n \ge 1$$ I have to find the value of $a$ ...
-2
votes
3answers
30 views

Having difficulty solving a recurrence relation

Given that $a_{n+1}=\dfrac{a_{n-1}}{1+n\cdot a_{n-1}a_{n}}$ for $n=1,2,3,....$ and $a_0=a_1=1$. Find the value of $a_{199}\cdot a_{200}$. Also give with proof the general formula of $a_{n}a_{n+1}$?
2
votes
1answer
76 views

An interesting subring of $\Pi \mathbb{Z}$

Let's look at this set ($e_{i}=(\delta_{ij})_{j}$ for all $i,j\geq0$ (kronecker delta)) $R_{\mathbb{Z}} =$$\{\sum_{i=0}a_{i}e_{i}$ : $a_{i}\in \mathbb{Z}$ $ \land$ $ \exists k,A_1,A_2,A_3,...,A_k\in\...
0
votes
2answers
43 views

How to obtain a formula for $f(z)$ given this recurrence

I am trying to figure out how to derive a formula for $f(z)$ that is a function of $z$ and maybe $k \in \mathbb{N}$: $$ f(z) = 1+z f \bigg(\frac{z}{1+z} \bigg) $$ As an attempt, I tried a change of ...
0
votes
2answers
36 views

How long until equilibrium between two recursive functions?

Problem I'm trying to figure out how long it takes Particle A and Particle B to reach an equilibrium in their temperatures. I've simplified this down to a pair of recursive functions. Let's say that ...
1
vote
2answers
29 views

Doubt on a recurrence equation

I have the following recursive equation for a pmf $P(s)$: $$P(s+1)=2 \lambda (1-\lambda) P(s)+ \lambda^2 \sum_{s'=0}^s P(s') P(s-s')$$ Here $s$ is a natural number and I have two initial conditions $P(...
1
vote
1answer
47 views

Prove that the recurrence relation $b_k = -4 \frac{n}{k} \left( b_{k-1} + b_{k-2} \right)$ is never zero.

Let the following recurrence relation be given: $b_0 = 1$ $b_1 = -4$ $b_k = -4 \frac{n}{k} \left( b_{k-1} + b_{k-2} \right)$ with $ k \leq n$ and $k,n \in \mathbb{N}$ $n$ is a constant. Question: ...
0
votes
2answers
82 views

Finding $\frac{I_1}{I_2}$ from recurrence relation

Consider following recurrence relation: $$2(\sum_{i = 0}^k I_{n-i}) + I_{n-k} = I_{n-k-1}$$ $k = 0 , 1 , \dots , n-1$ Also $I_0 = \frac{V}{R}$. Assuming that $n \ge2$ is a fixed integer, I'm ...
0
votes
3answers
43 views

Solve the recurrence: $T(n) = \sqrt{2n}T(\sqrt{2n})+\sqrt{n}$

I found a recurrence of a similar form on this forum, but I couldn't use it to gain any intuition for my question. So far, I've tried 3 things. I've tried unrolling it but could not really see a ...
-2
votes
2answers
23 views

what happens to this equation after change of variable?

I have the following equation $f$: $$ f(\frac{1}{z}) = 1 + \frac{1}{z} + \frac{1}{z(z+1)} + \frac{1}{z(z+1)(z+2)} + ... $$ If I make a change of variable $\frac{1}{z}=k$, does this mean that the ...

1
2 3 4 5
136