Questions tagged [recurrence-relations]

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

Filter by
Sorted by
Tagged with
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 $...
ksakerou's user avatar
-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.
Raj Ishu's user avatar
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(...
MathLearner's user avatar
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 ...
ryan f's user avatar
  • 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 ...
alice123019's user avatar
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 ...
alice123019's user avatar
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 ...
J P's user avatar
  • 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}$?
Notwen's user avatar
  • 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 ...
Batbold Egshiglen's user avatar
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 ...
Mats Granvik's user avatar
  • 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)...
youthdoo's user avatar
  • 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 ...
Yuriy S's user avatar
  • 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 ...
Irfan Ali's user avatar
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 ...
Elementary Only's user avatar
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 ...
Marco Ripà's user avatar
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 ...
robsmayer's user avatar
-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?
Prajjwal Dwivedi's user avatar
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 ...
yuki yuki's user avatar
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\...
Ninaaaaa's user avatar
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 $\...
Ashman Wadhawan's user avatar
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 ...
dank's user avatar
  • 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 ...
Ankit's user avatar
  • 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 ...
Cye Waldman's user avatar
  • 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}\...
Sherlock9's user avatar
  • 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 ...
Divakar's user avatar
-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 ...
RTV's user avatar
  • 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 ...
Cye Waldman's user avatar
  • 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 ...
jand's user avatar
  • 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$ ...
thefool's user avatar
  • 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 ...
Marko's user avatar
  • 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 $...
per persson's user avatar
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 ...
Данила Алексеев's user avatar
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 ...
Just another student's user avatar
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 ...
Chavez's user avatar
  • 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 ...
thefool's user avatar
  • 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 ...
Sahaj Satish Sharma's user avatar
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 ...
thefool's user avatar
  • 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 ...
thefool's user avatar
  • 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 ...
maplemaple's user avatar
  • 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)\\ ...
Cye Waldman's user avatar
  • 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 ...
mtheorylord's user avatar
  • 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)\ \ \ \ \ \ \ \ \ \ \ \ \ \...
ramind's user avatar
  • 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 ...
Maths's user avatar
  • 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?
Mohamed Mostafa's user avatar
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 ...
user123's user avatar
  • 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 ...
lesobrod's user avatar
  • 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 ...
thefool's user avatar
  • 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 ...
Il Prete Rosso's user avatar
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 ...
sandza's user avatar
  • 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 ...
Kamal Saleh's user avatar
  • 4,490

1
2 3 4 5
176