# Questions tagged [recurrence-relations]

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

8,797 questions
Filter by
Sorted by
Tagged with
30 views

1 vote
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 ...
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 ...
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 ...
21 views

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}{\left\{{#1}\atop{#2}\... 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 ... -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 ... 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 ... 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 ... 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 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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)\\ ...
130 views

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 ...
1 vote
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)\ \ \ \ \ \ \ \ \ \ \ \ \ \...
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 ...
1 vote
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?
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 ...
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 ...
1 vote
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 vote
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 ...
### 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 ...
### 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 ...