Questions tagged [recurrence-relations]
Questions regarding functions defined recursively, such as the Fibonacci sequence.
8,585
questions
1
vote
0
answers
17
views
Probability to reach $n+1>0$ before returning to the origin in an asymmetric one dimensional random walk.
Let's say we take one dimensional random walk. The origin is at point $0$ and next, there are $n+1$ integres, so we have: $0, 1, 2, 3, 4, ... n+1$. W start in the point $1$ from which we make a $1$ ...
- 363
1
vote
0
answers
22
views
Obtaining a single value of EGF in terms of multiple OGF evaluations?
I have access to ordinary generating function $f$ which I can evaluate at $d$ arbitrary real-valued points $f(s_1),f(s_2),\ldots,f(s_d)$. I need to know the approximate value of $g(t_1)$, which is the ...
- 4,990
1
vote
1
answer
31
views
Solve two-variable recursion using generating function
Suppose $T(n,k)$ satisfies the nitial condition $T(0,k)=\delta_{k,1}$ and the recursion
$$ T(n,0)=qT(n-1,1),\quad T(n,1)=qT(n-1,2),$$
$$ T(n,k)=qT(n-1,k+1)+pT(n-1,k-1), k>1.$$
Playing around, I ...
- 1,677
3
votes
2
answers
57
views
Does a bijective function exists behind every recurrence relation?
Consider these 2 questions where recurrence relations can be applied:
Q1) Given an (nxm) where n denotes rows and m denotes columns of a grid, find the number of unique paths ($a_{n,m}$) that goes ...
- 53
0
votes
1
answer
29
views
Why does this application of Jacobsthal numbers defined by the recurrence relation: $a_n$ = $a_{n-1}$ + 2$a_{n-2}$ work in 2D tiles / grids?
Problem Statement: Find the Recurrence Relation for $a_n$, where $a_n$ is the number of ways to tile a (2xn) rectangular board with (1x2) or (2x2) pieces.
.
.
Note: A (1x2) piece can be placed either ...
- 53
2
votes
1
answer
45
views
solution for reccurence relation, different solution than wolframalpha
I have reccurence relation:
$$a_n=\frac{1}{1-p}a_{n-1}-\frac{p}{1-p}a_{n-2}$$
Solving this using method from wikipedia, so plug $a_n=r^n$
$$r^2-\frac{1}{1-p}r+\frac{p}{1-p}$$
so $r_1=\frac{\frac{1}{1-...
1
vote
1
answer
75
views
Finding the formula for the Fibonacci numbers using Generating Functions
I am trying to derive the formula for the Fibonacci sequence. Here is my work, I am making a mistake somewhere, but I can't seem to find where it is. My answer is almost correct but the the final ...
- 89
0
votes
0
answers
30
views
Bounding the "General Version" of the Fibonacci Sequence
I am working on the following problem:
Define $\{a_n\}$ where $a_0=0$, $a_1=1$, and $a_n=A\cdot a_{n-1}+B\cdot a_{n-2}$ for all $n\geq 2$ where $A,B\in\mathbb{R}$. Find a constant $M$ such that $a_n\...
- 89
0
votes
0
answers
16
views
Recurrence Relation for Longest Increasing Subsequence Problem
I am trying to solve the Longest Increasing Subsequence(LIS) Problem using different OPT Function than the one which normally used. I have been given this question as an extra credit and I have been ...
- 1
2
votes
0
answers
54
views
Generating Function for the number of $n$-permutations whose square is the identity permutation.
I am learning the concept of generating functions and am working on the following problem:
Let $r(n)$ be the number of $n$-permutations whose square is the identity permutation. We proved that
$$r(n+...
- 89
0
votes
1
answer
18
views
Integral on union of two disjoint interval time scale
I am trying to solve a relatively simple integral on Time scales$\mathbb{T}$ in the book
Dynamic equations on Time scales.
It says evaluate $\int_0^t s \Delta s$ for $t \in \mathbb{T}$ for $\mathbb{T}=...
- 276
0
votes
0
answers
21
views
Can we prove the existence of an alternate multivariate recurrence relation if its variables are independent?
Apologies, it was difficult to find the right wording for this question. Please see the Discourse section for further elaboration on this.
Background
Univariate recurrence relations are defined nicely ...
- 101
-1
votes
0
answers
26
views
Solving Linear Non-Homogeneous Recurrence - where F(n) contains an exponential (2^n) and a polynomial (n+3)
.
.
.
What is the reason as to why we are allowed to "solve it one by one" (highlighted in red) ? - where we go on to consider 2^n (green) and n+3 (pink) of F(n) seperately and then find ...
- 53
2
votes
1
answer
42
views
Sum of the series created by a recursive sequence
$\{a_n\}$ and $\{b_n\}$ are two series of real number with $a_0=2$,$a_1=3$
and $a_{n+1}=3a_n-a_{n-1},\forall n\in \mathbb{N^+}$,when
$m= 2^n$, we have $\sqrt{b_n}=\frac{m}{a_m}$.Now, for the series
$$\...
1
vote
1
answer
42
views
Using inequality $\sum_{k-2}^{n-1} k \log k \leq \frac{1}{2} n^2 \log n - \frac{1}{8} n^2$ to show the recurrence of quicksort runtime
Use the inequality
$$\sum_{k=2}^{n-1} k \log k \leq \frac{1}{2} n^2 \log n - \frac{1}{8} n^2$$
To show that $$C_n = \frac{2}{n}\sum_{i=2}^{n-1}C_i + \Theta(n)$$ is $\Theta(n \log n)$
This is an ...
- 1,329
0
votes
1
answer
58
views
Solve a 2D linear recurrence
I need to know the solution of this recurrence:
$$2a[n,k-1]-a[n-1,k-1]-2a[n-1,k-2]+a[n-2,k-2]=a[n,k]$$
With the initial value unspecified.
Also, wolfram is good at solving linear 1D recurrence, but ...
0
votes
1
answer
54
views
Set theory exam question on infinite union of relations [closed]
Let $R$ be any relation over $\mathbb Z$ (the integers). Let $R_n $ be the set of all relations $ R $ (over the integers) such that $n$ is natural, by:
$
R_0:= R$.
$R_{n+1}:= R_n \cup (R_n ◦ R_n)$.
$...
- 3
0
votes
3
answers
43
views
I was wondering how can we prove that a recurrence relationship depending on the two previous terms is actually the sum of two geometric sequences
I was working on a problem and I stumbled upon this equality:
$a_{n+2} = a_{n+1} + a_{n}$
And I'm trying to find the general expression of the sequence $a$.
For this, I wanted to show that $a$ can ...
- 1
0
votes
0
answers
22
views
Is there a theorem about the existence of a closed form solution for a recurence relation?
I don't know much about recurence relations in theory (they usually pop up on my radar when solving differential equations). I was wondering is there any theorem about the existence of closed-form ...
- 1,200
0
votes
1
answer
70
views
How to discover the relation between 4096 and 729 as result of 10 billions of simulations. [closed]
First of all I'm not mathematician (really admire them), but programmer. My question come from the result or analysis from 10 billions simulations on an specific ...
- 119
0
votes
0
answers
24
views
(Code implementation of) Gosper's algorithm for sums (of catalan numbers) that are dependent on end-point
I'm working on my understanding of Catalan numbers and recurrence relations in general. In trying to prove they satisfy a certain recurrence relation, I wanted to find a telescoping sequence to ...
- 1
0
votes
1
answer
29
views
A Bessel functions related reccurence
Working on my research i came upon the following recurrence relation, which looks extremely similar to the Bessel function recurrence, but has a slight twist where a derivative is present:
Is there a ...
- 35
0
votes
0
answers
93
views
Solve the recurrence $T(n)=T(n-3)+\frac1{\log n}$
We must solve the recurrence $T(n)=T(n-3)+ \frac{1}{\log {n}}$ using substitution.
I've got up to here
$$T(n)=T(n-3-3)+\frac1{\log(n-3)} + \frac1{\log n} \implies T(n-3-3-3) + \frac1{\log(n-3-3)} + \...
3
votes
1
answer
64
views
How many numbers of base 3, of length $n$ are there that contain at least $1$ twos
My Attempts
First I wrote down some numbers
Of length one, there is only $1$ valid number - $2$
Of Length two there are $4$: $12, 20, 21, 22$
Of Length three there are $13$: $112, 120, ... , 221, 222$...
- 33
2
votes
1
answer
63
views
Solving a 3 variable recurrence relation in which the variables swap around
I was looking into a recurrence relation related to the Tower of Hanoi and how many times a particular $a,b,c$ appears where $a$ disks are on the left peg, $b$ disks are on the middle peg, and $c$ ...
- 185
4
votes
1
answer
121
views
Limits of recursions like $f(n+2)=\frac{1}{f(n)} - \frac{1}{f(n+1)}$ !?
Consider the sequences
$$f(0)=1,f(1)=2$$
$$f(n+2)=\frac{1}{f(n)} - \frac{1}{f(n+1)}$$
$$g(0)=1,g(1)=2,g(2)=3,g(3)=4$$
$$g(n+4)=\frac{3}{g(n)} - \frac{3}{g(n+1)} + \frac{3}{g(n+2)} - \frac{3}{g(n+3)}$$
...
- 13.6k
1
vote
1
answer
76
views
let $f(x)$ is polynomial function , $f(x+2)-f(x) = 6x^2+12x$ , $f(1)-f(0)=?$ [closed]
Let $f$ is polynomial function.
$$f(x+2)-f(x) = 6x^2 +12x$$
$$f(1)-f(0)=?$$
I found that $f(x)$ is 3rd order ,
and use some coefficient $a, b, c, d$, but that's too hard to solve.
I want to use ...
- 43
5
votes
3
answers
111
views
Closed form of the recursion formula for $\int_{0}^{1} \ln^r(1-x)x^n \, dx$
It is easy to see that we have the following recursive formula for the indefinite integral of log powers:
$$J_r := \int \ln^r(1-x) \, dx \stackrel{\text{sub.}+IBP}{=} -(1-x)\ln^r(1-x) - r\int \ln^{r-1}...
- 766
2
votes
1
answer
73
views
What is the probability of 3 or more consecutive successes in N trials
Let the probability of a success in a trial be $p$ (let $q = 1-p$).
We want to know $P(n)$, the probability of 3 (or more) consecutive successes happening at least once in $n$ trials.
$P(3)$ is $p^3$
$...
- 21
3
votes
1
answer
62
views
On the limit defined by $A + B(A + B(A + B (A + B(\cdots))))$
Suppose $A$ and $B$ are some constant ($A,B\in\mathbb{R}$)
Is there a simple expression for $x$, where $x$ is:
$$
x=A+B[A+B[A+B[\cdots]]]]
$$
"..." indicates the pattern repeats forever.
In ...
- 152
0
votes
0
answers
27
views
Concrete Mathematics - The Josephus Problem for $J(2^m)=1$
I've been going through Concrete Mathematics and have a question on the Josephus problem.
Recurrence relation:
$$\begin{split}
J(1)&=1\\
J(2n)&=2J(n)−1\\
J(2n+1)&=2J(n)+1
\end{split}$$
...
- 1
0
votes
1
answer
36
views
What will be the base case here in this recurrence relation?
Problem:
Lorenzo takes up a loan of 40,000. It is to be paid by annual installments of 2000 with first payment made at the end of the first year the loan was taken out. 3% interest is charged at the ...
- 2,923
0
votes
0
answers
30
views
Solving a recursive equation [duplicate]
So I'm working on a combinatorics problem, to which I've reached that $$f(1)=1, f(n)=1+\frac{1}{n}\sum_{k=1}^{n-1} f(k)$$
I have been working at this problem for a few days now, and I am fairly ...
- 47
1
vote
1
answer
44
views
General expression for function defined recursively
I try to have a general expression of a sequence of functions defined as follow :
$$u_0=f ~\text{and}~ \forall n >0, u_{n+1} =-f\times u_n + \frac{du_n}{dt} $$
where $f\in \mathcal{C}^\infty(\...
- 151
2
votes
0
answers
43
views
numerical approaches to functional equations
I'm interested in finding numerical approaches to solving functional equations such as
$$f(xy) = f(x)+f(y),$$
where the equations had no derivatives or integrals, and contains arguments involving $x$ ...
- 1,688
2
votes
0
answers
42
views
How to compute $\sum_{r=0}^N \frac{N!}{(N-r)!}$? This quantity is the count of $r$-permutations of $N$ items (for $r$ ranging from $0$ to $N$). [duplicate]
Given $N$ items, how many $r$-permutations are there (for $r$ ranging from $0$ to $N$)?
There is $1$ $0$-permutation (the empty permutation).
There are $N$ $1$-permutations.
There are $N(N-1)$ $2$-...
- 1,347
0
votes
2
answers
67
views
Solving the following recurrence equation $T(n) = T(n-2)+n^2$, having $T(0)=1$, $T(1)=5 $
Solve the following recurrence equation: $T(n) = T(n-2)+n^2$, having $T(0)=1$, $T(1)=5$.
I need to solve this equation but when I get to the particular solution with $n^2$ some of the terms I need ...
- 1
1
vote
1
answer
74
views
Three-term recurrences in Orthogonal polynomials
hi I am reading one lecture note about Orthogonal polynomials (https://www.math.hkbu.edu.hk/ICM/LecturesAndSeminars/08OctMaterials/1/Slide2.pdf)
and there's one step in the proof in "Three-term ...
- 53
1
vote
1
answer
33
views
An verification about the solution of problem relating recursive relations
I want to check that whether my method of solving this problem is right. Here is my solution:
I want to use inclusion-exclusion to solve this.
Suppose
$P_1=$ the case that I put one of the elements ...
- 1,237
1
vote
2
answers
68
views
Proving Generating Function holds a specific recurrence.
Consider the generating function $$\dfrac{1}{1 − 2x − x^2} = \sum_{n=0}^{\infty}a_nx^n$$
Prove that for each integer $n \ge 0$,
$$a_n^2+a_{n+1}^2 = a_{2n+2}$$
Hint: Find a $2 \times 2$ matrix $A$ such ...
- 79
0
votes
0
answers
29
views
Derivation of inequality using inequality identities
I am trying to derive an inequality formula found in in one paper regarding the proof of stability of a discrete-time control scheme. Consider the following expression of the closed-loop tracking ...
- 207
0
votes
1
answer
60
views
Proving the convergence and finding the limit of a sequence
I am having trouble proving the convergence and finding the limit of the sequence $\left(a_{n}\right)$ given by $a_{1}=\sqrt{3}$ and $a_{n}=\sqrt{3+2 a_{n-1}}$. I need to show that the sequence is ...
- 111
4
votes
2
answers
132
views
Find the value of $x_1$ [duplicate]
The positive numbers $x_1,x_2,\cdots,x_n$ $n\ge3$ satisfy $$x_1=1+\frac{1}{x_2},x_2=1+\frac{1}{x_3},\cdots,x_{n-1}=1+\frac{1}{x_n}$$
And also $$x_n=1+\frac{1}{x_1}$$
Find the value of $x_1.$
My first ...
1
vote
0
answers
20
views
Using recurrence relation to solve difference equation
I came across this exercise that says,
Show that for any constant $c$, $$u(t) = ca^t \frac{\Gamma(t-t_1)\Gamma(t-t_2) \cdots\Gamma(t-t_n) }{\Gamma(t-s_1)\Gamma(t-s_2) \cdots\Gamma(t-s_m)}$$ is a ...
- 276
0
votes
1
answer
65
views
Find the explicit formula for this recurrence relation [closed]
Solve this recurrence relation:
$$a_0 = 1$$
$$a_n = 2^{2(5-n)+1}* a_{n-1} + 1$$
We've only covered linear homogeneous recurrence relation in our course so I'm a little lost and any help would be ...
- 29
1
vote
1
answer
30
views
Recursion with convergent coefficients
Suppose that we have a linear recurrence $x_{n+1}=a_n x_n + b_n x_{n-1}$, such that $a_n\to a$ and $b_n\to b$, and where the roots $\lambda_1,\lambda_2$ of $x^2-ax-b=0$ are distinct real roots with $0&...
- 7,755
0
votes
1
answer
94
views
Proof of alternating zeros of Bessel function
We will be dealing with the Bessel functions of the first kind. Notice that to prove that their zeroes are alternating, one can just prove that for every two zeroes for $J_\nu(x)$ there exists a zero ...
- 1,789
0
votes
1
answer
31
views
A Bessel function inspired recurrent sum
I came up upon the following recurrent sum.
$a\cdot (B_{n-1}\cdot e^{i\cdot k_0 \cdot z}+ B_{n+1}\cdot e^{-i\cdot k_0 \cdot z})=2 \cdot n \cdot B_n$
Where $a$ is complex , $k_0$ and $z$ are real, $n$ ...
- 35
0
votes
0
answers
87
views
Prove the recurrence relation $T(n) = 2T(n/2) + n$ is equal to $n\log(n) + n$ using induction
Question
Given the recurrence relation for the Merge Sort algorithm:
$T(n) = 1$, if $n = 1$
$T(n) = 2T(n/2) + n$, if $n > 1$
Prove by induction that $T(n) = n\log(n) + n$ and hence $O(n\log(n))$
My ...
0
votes
0
answers
56
views
Can we get a recurrence relation for this sum?
Suppose
$S_k = \sum_{i=0}^k \binom{k}{i} \frac{\left(a\right)_i\left(b\right)_{k-i} x^i}
{\left(c\right)_i\left(d\right)_{k-i}}$,
where $(a)_i = a(a+1)\cdots (a+i-1)$.
Note that the above sum can also ...
