Questions tagged [recurrence-relations]
Questions regarding functions defined recursively, such as the Fibonacci sequence.
8,797
questions
0
votes
0
answers
30
views
How to solve this type of recurrent relations using generation functions?
I have no idea how to solve this relation, when $n$ in
$(n+2)^2\cdot g(n+2)+g(n)=0$ using generating functions, not induction (this exercise meets me in generating functions method paragraph I tried $...
- 1
-3
votes
0
answers
26
views
Solving the recurrence relation $\,T(n) = n T(\sqrt n) + n$.
$$T(n)=\begin{cases}2, & \text{if } \, n\le2,\\
nT(\sqrt n) + n, & \text{if } \, n>2 \end{cases}.$$
I have tried it but at last, it is getting very complex. Please help me in solving this.
- 7
4
votes
1
answer
71
views
Finding the asymptotic of the sequence $a_{n+1}=a_n+\frac{1}{f(a_n)}$
We define $f(x)$ be a differentiable function with $f^\prime\ge 0$, $f^\prime$ bounded and $f\to+\infty$ when $x\to+\infty$. Define the sequence $\{a_n\}$ as follows:
$$a_0=1, a_{n+1}=a_n+\frac{1}{f(...
- 77
2
votes
1
answer
75
views
Solving a floored recurrence relation $F_n = c \cdot \left\lfloor \frac{F_{n-1}}{d} \right\rfloor$
I initially wanted to solve the following recurrence relation:
$$F_n = c \cdot \left\lfloor \frac{F_{n-1}}{d} \right\rfloor \text{ for } F_0, c, d \in \mathbb{N} \tag{1}$$
Out of interest, I've also ...
- 338
2
votes
2
answers
83
views
Show $P_n = \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \dots + \frac{(-1)^n}{n!}$ given $P_n = \frac{n-1}{n} P_{n-1} + \frac1n P_{n-2}$
Show that $P_n = \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \dots + \frac{(-1)^n}{n!}$ given $P_n = \frac{n-1}{n} P_{n-1} + \frac1n P_{n-2}$, $P_1 = 0$, $P_2 = \frac12$
I have absolutely no clue ...
- 133
0
votes
2
answers
43
views
The matching problem in a recursive view
Suppose there are n people invited to a party. Seats are assigned and a name card is made for each guest. However, floral arrangements on the table unexpectedly obscure the name cards. When the n ...
- 133
0
votes
0
answers
24
views
Optimizing a recurrence relation for a sequence
Given the sequence $$a_k=\frac{(2k)!}{4^k(k!)^2(2k+1)}(0.5)^{2k+1},$$ I should find a recurrence relation for it. I came up with $a_0 = 0.5$ and $$a_{k+1}=\frac{(2k+1)^2}{8(k+1)(2k+3)}a_k.$$ is there ...
- 35
-1
votes
2
answers
57
views
How to find a closed-form expression for the sequence $x_n = x_{n-1}(1.1) + 100$
I have the sequence $\mathbf{x_n = x_{n-1}(1.1) + 100}$ with $\mathbf{x_0 = 100}$.
How can I calculate $\mathbf{x_n}$ as an explicit function of $\mathbf{n}$?
- 35
-3
votes
1
answer
75
views
how to solve the recurrence relation $(n+1)a_n=(n+3)a_{n-1} + n, n\ge 1$ [closed]
I don't really know how to solve it, but it would be a pleasure if you solve it. I worked on this problem for like 4 hours and still didn't find any solution. Sorry if my problem looks like it didn't ...
0
votes
0
answers
43
views
What is the name for a matrix which is generated by a recursive sum whose form equals a recursive product when replacing the sums with products?
In this answer to the question "Do these series converge to logarithms?" it is shown by George Lowther that each Dirichlet series involving the pattern of divisors converge to $\log(n)$ in ...
- 7,286
0
votes
3
answers
69
views
Find least $\lambda$ for which recursive sequence is always positive
Find the least $\lambda$ for which the sequence $\{b_n\}$ defined by $b_1=1$, $b_2=\lambda-1$ and $b_{n+2}=\lambda(b_{n+1}-b_n)$ is always positive.
I guess $\lambda=4$, which yields $b_n=2^{n-1}(n+1)...
- 705
3
votes
1
answer
85
views
A general integral equality $\int_{0}^{\infty}e^{-sx}\frac{\mathrm{d}x}{\left(1+x^{2}\right)^{a/2}}\left[s+\frac{ax}{1+x^{2}}\right]=1$
How can we prove this integral equality:
$$\int_{0}^{\infty}e^{-sx}\frac{\mathrm{d}x}{\left(1+x^{2}\right)^{a/2}}\left[s+\frac{ax}{1+x^{2}}\right]=1 \tag{1}$$
I found it in a very roundabout way, but ...
- 31.1k
-3
votes
0
answers
25
views
$2$nd order q-Difference Equation [closed]
I am trying to find the solution of the following q-Difference equation
$$y(q^2x) - (q^n + q^{-n})y(qx) + \left(1 -\frac{(1-q^2 )^2 x^2}{4}\right)y(x) = 0$$
I have been using several polynomials like ...
1
vote
0
answers
66
views
Explicit expression of $1^k+...+n^k$ from the recursive definition.
Fix an integer $n\in \Bbb{Z}^+$. For non-negative integer $r$ define the sum $$S_r = 1^r+2^r+...+n^r.$$
From the equality
$$(m+1)^{k+1}-m^{k+1} = \binom{k+1}{1}m^k+...+\binom{k+1}{k}m+1$$ sum up both ...
0
votes
0
answers
28
views
Final digit of $a[n]a$, where $[n]$ is the $n$-th hyperoperator and $a \in \mathbb{Z}^+$
While I was submitting a few sequences to the OEIS, I noticed an asymmetrical pattern involving the rightmost digits of an interesting set of well-known integer sequences.
Let $a \in \mathbb{Z}^+$, $n ...
- 703
0
votes
0
answers
18
views
How can I represent a decreasing summation which the highest value is the starting value?
I am trying to find the recurrence of
$ T(n) = 2T(n-1) + n^2$ The answer it's $O(2^n n^2)$ but now I'm trying to find the answer using recursion and all good, but trying to find $T(n-k)$ is killing ...
-1
votes
0
answers
28
views
Solving Tn=Tn-1 +Tn-2 recurrence relation
If the recurrence relation is T(n)=T(n-1)+T(n-2),can we find T12 in terms of T1 and T2 without just expanding the expression and putting the value?
0
votes
0
answers
35
views
Discrete Schrodinger Equation - Solution as Bessel functions
Consider the DSE with no nonlinearity term: $$i\partial_{z}(q_n(z)) = q_{n+1}(z) + q_{n-1}(z)$$ I want to solve this exactly and have been told it can be done with Bessel functions, but I do not see ...
1
vote
0
answers
63
views
Solving $T(n) = T(n/2) + T(n/3) + n$
Show that the solution to the recurrence relation
$$T(n) = n \;\;\;\;\text{ for }\; n=1,2$$
$$T(n) = T(n/2) + T(n/3) + n \;\;\;\;\text{ for }\; n > 2$$
is $O(n)$ using substitution.
$$T(n) \leq c\...
- 11
1
vote
0
answers
97
views
solving question on recurrence relation and sumation
Let $\{x_{n}\}$ be a sequence of non-negative real numbers such that $x_{n + 1}^2 =6x_{n} +7$ for all $n ≥ 2$
Which one of the following is true?
$\quad(A).\space$ If $x_{2} > x_{1} > 7$ then $\...
1
vote
1
answer
51
views
How to obtain a recurrence relation for Taylor series coefficients?
Recently, I asked WolframAlpha to give me the first few terms in the Taylor series for a complicated (but well-behaved) function. It did so, but also provided a recurrence relation for the ...
- 13
0
votes
2
answers
56
views
Solving the recurrence relations with boundary conditions
This is the recurrence relation:
$$a_r - 4a_{r-1} + a_{r-2} = 1 + 2^r$$
and we have to solve this with boundary conditions $a_0 = 1$ and $a_1 = 2$.
I found the complementary solution, made the ...
- 224
0
votes
0
answers
35
views
How do we prove this nested radical solution?
I’m submitting this question because my previous one was perhaps too verbose and did not get the point very quickly.
A well known $\sqrt{2}$ nested radical has the following solutions as found in the ...
- 6,791
0
votes
0
answers
21
views
Stirling numbers of second kind recurrence relation on $k$
In my previous question on the properties of $\sum_{k=0}^nk^a\binom{n}{k}$, a comment directed me to the answers on this related question with formula $$
\newcommand{\stirtwo}[2]{\left\{{#1}\atop{#2}\...
- 235
0
votes
0
answers
56
views
Cyclic Powers of Special Numbers
consider the number -1, i can say it is a special number because the powers of (-1) is always 1 or -1.Generally $(-1)^n = 1$ if n(mod 2) = 0 and $(-1)^n = -1$ if n(mod 2) = 1.
my question is that is ...
- 1
-3
votes
0
answers
48
views
I want to prove for the Fibonacci sequence, without using induction that $F_n < 2^n$ [closed]
I know how to prove it by two step induction, but I wanted to prove it using only the recurrence relation:
$F_n = F_{n-1} + F_{n-2}$
$F_0=1$
$F_1=1$
I really don't know where to start thinking about ...
- 1
0
votes
0
answers
16
views
A Nested Radical Arising from a Nonlinear Recurrence
I have been looking into analytic continuation of regular recurrence relations into the negative, real, and complex domains ($\mathbb{N} \mapsto \mathbb{Z}, \mathbb{R},\mathbb{C}$). In doing so, we’ve ...
- 6,791
0
votes
2
answers
83
views
Every term in a recurrence is an integer
Let $a_1:=1$, $a_2:=10$. For $n > 2$, define:
$$a_n:=\frac{a_{n-1}^2-1}{a_{n-2}}$$
Show that every $a_n \in \mathbb Z$.
I computed a couple terms and indeed they all seem to be integers, but I'm at ...
- 21
2
votes
0
answers
65
views
There two types of tiles, we need to construct a $2 \times n$ rectangle filled with them. How many ways are there to do that?
Two types of tiles are defined:
tile $B$: a simple $1 \times 1$ sqaure tile,
tile $B$: we divide a $2×2$ square tile with segments connecting the centers of opposite sides into four $1 \times 1$ ...
- 1,047
1
vote
1
answer
18
views
Expected Value MnMs, why does my equation not work?
I was trying to do this question but with a recurrence relation for the Expected Values
https://puzzling.stackexchange.com/questions/7900/the-mm-sugar-rush-game
Suppose I have in my possession a ...
- 39
1
vote
1
answer
54
views
Particular solution of recurrence relation $y_{n+2}-6y_{n+1}+9y_n=2*3^{n+2}$
I am trying to find a particular solution of $y_{n+2}-6y_{n+1}+9y_n=2*3^{n+2}$. I set $y_n=A3^{n+2}$ and get $A3^{n+4}-6A3^{n+3}+9A3^{n+2}=A^{n+2}(9-18+9)=2*3^{n+2}$.
So do I need another guess for $...
- 645
2
votes
0
answers
54
views
Which branch of math theory could solve the task?
Imagine that we have a value $s_i = f(s_{i-1}, x_{i-1})$, reccurent formula $s_i$ with parameter $x_i$. $x_i$ values depends on $x_0$ and each $x_i$ is calculated in a diffenrent way. I guess it is ...
- 121
0
votes
0
answers
31
views
Proving Recursive Sequence Identities and Limits
I've been having trouble with this homework problem for some time. I believe that I need to prove the identity statements by induction, but I'm not sure what that would look like. Similarly, I have ...
3
votes
1
answer
92
views
Proof of convergence of a Fibonacci-like sequence $\frac{1}{u_{n+1}} = \frac{1}{u_n} + \frac{1}{u_{n-1}}$
I was exploring a Fibonacci-like sequence,
$$\frac{1}{u_{n+1}} = \frac{1}{u_n} + \frac{1}{u_{n-1}}$$
Solving it directly, $u_n=(A(\frac{1+\sqrt5}{2})^n+B(\frac{1-\sqrt5}{2})^n)^{-1}$ which converges ...
- 359
1
vote
0
answers
34
views
Children face each other in two rows of $n$ people. The childern hold hands in different schemes. Count them (recurrence solution verification)
During preschool game, children face each other in two rows of $n$ people. Each child holds with its right hand:
the hand of the child opposite to them or
the hand of the neighbor to the right or
the ...
- 1,047
0
votes
1
answer
42
views
Tiling with limited number of tiles.
Consider a $2 \times n$ grid that is to be tiled with up to $n$ tiles of dimensions $2\times 1$ and up to two tiles of dimensions $2\times 2$. Rotation of tiles is not allowed. In how many ways can ...
0
votes
0
answers
37
views
There are $7$ different types of lunch dishes at the bar: $3$ for $1 \$ $ each, $4$ for $2 \$ $ each. We plan to eat lunch until we use $n$ dollars
There are $7$ different types of lunch dishes at the bar:
$3$ for $1$ dollar each,
$4$ for $2$ dollars each.
We plan to eat lunch there for the next few days, consisting of one dish every day, until ...
- 1,047
5
votes
3
answers
109
views
n students standing in line are to be divided into teams and in each team appointed a captain. How many ways to do that? (I need last transformation)
There are $n$ students in the class. They stand in a line in front of the teacher, who is to divide them into any number of non-empty teams (in particular, the sets can be of size $1$ or $n$) and in ...
- 1,047
2
votes
2
answers
71
views
Analytic solution for number of paths with length $k$ on an $n \times n$ Chessboard allowing Self-Intersecting?
Consider an $n \times n$ chessboard where the journey begins at the bottom-left corner $(1, 1)$ and concludes at the top-right corner $(n, n)$. How many distinct paths are available that necessitate ...
- 1,085
0
votes
0
answers
36
views
Problem reconciling a recurrence, $g(n)=\sin(n-1)g(n-2)$ with closed form
Consider the recurrence relation in the title and its solution by induction.
$$
\begin{align}
&g(n)=\sin(n-1)g(n-2),\quad g(0), g(1) \text{ given}\\
&g(2)=\sin(1)g(0)\\
&g(3)=\sin(2)g(1)\\
...
- 6,791
2
votes
2
answers
130
views
Quadratic Recurrence Relations
Does anyone know combinatoric methods to get solutions to quadratic recurrences? An example of what I'm looking for:
$$F_{n+1} = 3F_n^2-2F_n$$
under the initial condition $F_0 =2, F_1 = 8$.
Much more ...
- 4,182
1
vote
0
answers
59
views
Cancelling terms in an infinite series over $\mathbb{N}^2$
I try to understand Don Zagiers seemingly simple proof of the recurrence relation
\begin{align*}
\sum_{0<j<k,\ j\ \text{even}}\zeta(j)\zeta(k-j)=\frac{k+1}{2}\zeta(k)\ \ \ \ \ \ \ \ \ \ \ \ \ \...
- 11
4
votes
1
answer
67
views
A sequence is defined $P_n(x)=P_{n-1}(x-1)P_{n-1}(x+1)$for $n\ge1$ and $P_0(x)=x$. Find the largest $k$ such that $P_{2014}(x)$ is divisible by $x^k$.
I started by finding some of the polynomials and got $$P_1(x)=x^2-1$$$$ P_2(x)=x^2(x^2-4)$$$$ P_3(x)=(x^2-1)^3(x^2-9)$$$$P_4(x)=x^6(x^2-4)^4(x^2-16)$$$$P_5(x)=(x^2-1)^{10}(x^2-9)^5(x^2-25)$$ but I’m ...
- 499
1
vote
1
answer
64
views
What field should I search to solve delay like equations?
I want to solve equations like:
$$
t f(t) + u(t-2) f(t-2) = \sin(t)
$$
It's like delay differential equations but without the derivative.
What field should I search in to solve this kind of equation?
- 1,118
3
votes
2
answers
80
views
$\Theta$-notation of the recurrences $T(n) = 3T(n/2 +1) + n$ and $T(n) = 4T(n/2)-4T(n/4)+1$ [closed]
(a) $T(n) = 3T \left ( \frac{n}{2} + 1 \right ) + n$
(b) $T(n) = 4T \left ( \frac{n}{2} \right ) - 4 T \left ( \frac{n}{4} \right ) + 1$
I am really stuck on these two recurrences and finding out ...
- 33
2
votes
0
answers
39
views
Properties of substitution system
I'm interested in automatic sequence or substitution systems.
I focused on the simplest form with a binary alphabet without constants.
A well-known example is Thue-Morse sequence
with axiom ...
- 770
1
vote
1
answer
56
views
Number of sequences of length $n \geq 1$ with elements from set $ \{0,1,2,3,4 \} $ such that blocks of $0$s, $2$s and $4$s are of even length.
Question statement:
In a sequence $\langle a_1, ...,a_n \rangle$ a block is every maximal subsequence of same digits. For example, in a sequence $\langle 0, 0, 3, 1, 2, 2, 2, 2, 4, 4 \rangle$ there ...
- 1,047
1
vote
1
answer
40
views
Recurrence and Asymptotic
Given this recurrent relation
$$a_{n+1} \leq a_n-ka_n^2,\ k>0$$
How can I prove this asymptotic behavior not using induction?
$$a_n\leq\frac{1}{nk+a_0^{-1}}$$
I ran this numerically on MATLAB and ...
- 171
0
votes
0
answers
21
views
Diophantine just with a recurring solution $XY=a^2(ab+1)=K$ (without calculating all K divisors)
I am trying to get a recurring solutions for this kind of Diophantine equation:
$XY=a^2(ab+1)=K$; where $a,b \in$ $\Bbb N$ and $a=even$
First of all, I am industrial engineer, sorry for that :) and if ...
- 1
3
votes
2
answers
149
views
Prove that $\lim_{n\rightarrow\infty}\frac{f(n)}{n!}=e$
Prove that $$\lim_{n\rightarrow\infty}\frac{f(n+1)}{n!}=e\tag{1}$$where $$f(n+1)=n(1+f(n))$$
The recurrence relation of $n!$ is $a_n=na_{n-1}$ or $a_{n+1}=(n+1)a_n$. I thought of making a new ...
- 4,490