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

learn more… | top users | synonyms (2)

7
votes
3answers
4k views

I have a problem understanding the proof of Rencontres numbers (Derangements)

I understand the whole concept of Rencontres numbers but I can't understand how to prove this equation $$D_{n,0}=\left[\frac{n!}{e}\right]$$ where $[\cdot]$ denotes the rounding function (i.e., ...
7
votes
8answers
993 views

Need help deriving recurrence relation for even-valued Fibonacci numbers.

That would be every third Fibonacci number, e.g. $0, 2, 8, 34, 144, 610, 2584, 10946,...$ Empirically one can check that: $a(n) = 4a(n-1) + a(n-2)$ where $a(-1) = 2, a(0) = 0$. If $f(n)$ is ...
7
votes
6answers
400 views

Finding the $n$-th deriviative of $f(x) =e^x \sin x$, solving the recurrence relation

I was given a homework assignment to find a closed solution for the nth deriviative of the function: $f(x) = e^x \sin x$ So far I have been able to obtain the derivative as: $f^{(n)}(x) = e^x S_n ...
7
votes
5answers
557 views

How does one find a formula for the recurrence relation $a_{1}=1,a_{2}=3, a_{n+2}=a_{n+1}+a_{n}?$

I am self-studying Discrete Mathematics, and I have two exercises to solve. Find a formula for the following recurrence relation: (translated from Portuguese) a) $a_{1}=3,a_{2}=5, ...
7
votes
3answers
521 views

Common term for differential equations and recurrence relations

Recently I have been working with recurrence relations (mostly linear), and systems of coupled recurrence relations. I have noticed a lot of common ground with differential equations. In a way, you ...
7
votes
1answer
96 views

Is there any explicit formula for $x_n$?

Let $a$ be a positive real number and $(x_n)$ be the sequence given by $x_1>0,$ $$x_{n+1}=\dfrac{1}{2}\Big(x_n+\dfrac{a}{x_n}\Big).$$ We can prove that $x_n\to\sqrt{a}$ as $n\to\infty.$ My ...
7
votes
2answers
244 views

Does anyone recognise this recursion sastisfied by the Bell numbers?

I derived a recursion $$B_n=\frac{1}{n}B_0+\frac{1}{n}\sum_{k=1}^{n-1}\left[\binom{n}{k}-(-1)^{n-k}\binom{n}{k-1}\right]B_k\tag{$*$}$$ which I know should be satisfied by the moments of the unit ...
7
votes
1answer
311 views

How prove that $x_1 = x_{2000}$ implies $x_2 \ne x_{1999}$, where $x_{n+2}=\frac{x_{n}x_{n+1}+5x^4_{n}}{x_{n}-x_{n+1}}$?

Let $x_{1},x_{2},\cdots$ be real numbers, such that for $n \ge 1$: $$x_{n+2}=\dfrac{x_{n}x_{n+1}+5x^4_{n}}{x_{n}-x_{n+1}}$$ If $x_{1}=x_{2000}$, prove that $x_{2}\neq x_{1999}$. my idea ...
7
votes
5answers
409 views

The sum $\sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} x^j$

A recent answer of mine to a question on Math Overflow includes the sum $$S(n,k,x) = \sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} x^j,$$ where $\left\{ j \atop k \right\}$ is a Stirling number ...
7
votes
3answers
401 views

Why computing Fatou coordinate is so hard?

I'm trying to make images of Fatou coordinate for some polynomial maps. If I'm not wrong there is no explicit general formula/method for computing Fatou coordinate near parabolic fixed point. Is ...
7
votes
4answers
348 views

How can I solve this linear recurrence relation?

My problem is: this given recurrence relation: $$y_{n+1}-\frac{n+2}{2}\cdot y_n = (n+1)(n+2)\cdot 3^n$$ for all: $n\ge 0$ and $y_0 = 0$ I need to find the explicit form and the general solution. My ...
7
votes
1answer
1k views

Methods to find the limit of a sequence defined by a recurrence

For a sequence defined by a formula normally the usual limit rules allows one to find its limit. But for a sequence defined by a recurrence, up to now I have only seen some refined ad hoc methods, ...
7
votes
2answers
2k views

Numerical method for finding the square-root.

I found a picture of Evan O'Dorney's winning project that gained him first place in the Intel Science talent search. He proposed a numerical method to find the square root, that gained him $100,000 ...
7
votes
3answers
341 views

Solving recurrence relation: Product form

Please help in finding the solution of this recursion. $$f(n)=\frac{f(n-1) \cdot f(n-2)}{n},$$ where $ f(1)=1$ and $f(2)=2$.
7
votes
3answers
131 views

Help me understanding logic behind limits of recurence relations

I was trying to understand how limits of recurence relations are working. I have one. $$a_0 = \dfrac32 ,\ a_{n+1} = \frac{3}{4-a_n} $$ So, from what i know, if this recurence relation has a limit, ...
7
votes
1answer
234 views

Finding $a_n$ for very large $n$ where $a_n = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3} $

I have a recurrence relation, $$ a_n = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3} $$ for $n>3$ and $a_1 = 0, a_2 = 0, a_3 = 1$ I have to find the value of $a_n$ for very large values of n. I tried ...
7
votes
2answers
1k views

Proof of clockwise towers of Hanoi variant recursive solution

This is from one of the exercises in "Concrete Mathematics", and is something I'm doing privately, not homework. This is a variant on the classic towers of Hanoi, where all moves must be made ...
7
votes
2answers
113 views

Is the sequence $x_{n+1} = \frac{x_n + \alpha}{x_n + 1}$ convergent?

Fix $\alpha > 1$, and consider the sequence $(x_n)_n \geq 0$ defined by $x_0 > \sqrt \alpha$ and $$x_{n+1} = \frac{x_n + \alpha}{x_n + 1}, n = 0, 1, 2, \dots$$ Does this sequence converge, ...
7
votes
1answer
355 views

Proving or disproving $f(n)-f(n-1)\le n, \forall n \gt 1$, for a recursive function with floors.

The Olympiad-style question I was given was as follows: A function $f:\mathbb{N}\to\mathbb{N}$ is defined by $f(1)=1$ and for $n>1$, by: ...
7
votes
1answer
351 views

What is the asymptotic behavior of a linear recurrence relation (equiv: rational g.f.)?

The question sounds simple: find the roots of the characteristic equation, take the one with the largest absolute value, and find its coefficient. Repeated roots do not substantially complicate ...
7
votes
3answers
1k views

Solving recurrence relation of form $T(n/2 + c)$

It is obvious that the Master Theorem cannot be applied to the recurrences of the following form: $T(n) = 4T(n/2 + 2) + n$ Since I am only interested in the $\theta$ bound of the recurrence and not ...
7
votes
1answer
132 views

Put a mouse to the last cell

We have (n=12) cells $C_1, C_2 ,\dots, C_{12}$ which are initially empty. At each step, we can do one of two operations: $\mathbf{P}$: Put only in the first cell $C_1$ 2 mice. $\mathbf{M}$: Move ...
7
votes
2answers
302 views

q-Analogue of the formula $x^n=\sum_k\left\{n\atop k\right\}(x)_k$.

The stirling numbers of the second kind satisfy the formula $x^n=\sum_k\left\{n\atop k\right\}(x)_k$, where $(x)_k$ is the falling factorial. Consider the $q$-analog recursive definition of the ...
7
votes
1answer
295 views

Common terms in general Fibonacci sequences

Mathworld notes that "The Fibonacci and Lucas numbers have no common terms except 1 and 3," where the Fibonacci and Lucas numbers are defined by the recurrence relation $a_n=a_{n-1}+a_{n-2}$. For ...
7
votes
1answer
308 views

How to prove this sequence of inequalities

The number $c_{g}(n)$ is defined by the recurrence \begin{equation} c_{g}(n) = c_{g}(n-1)+ (n-1)(n-2)c_{g-1}(n-2) , \end{equation} with $c_{0}(n)=1$ for any $n\geq 1$ and $c_{g}(n)=0$ if $n \leq 2g$. ...
7
votes
2answers
573 views

unorthodox solution of a special case of the master theorem

I am asking for references regarding a special case of the master theorem. This theorem seems to appear quite a lot on this site, prompting me to study it in more detail, e.g. see my posts here and ...
7
votes
1answer
200 views

Diagonal of the double sequence $(n+1)v_{h,n+1}-(2h+1)v_{h,n}-nv_{h,n-1}=0$

Update: it is not possible to reply to this question without additional information. My comment below: "I have to agree with you that one "cannot derive (2) from (1) alone". Now it seems to me that ...
7
votes
1answer
412 views

Generating function of words in a binary alphabet counting blocks and appearances

Given the binary alphabet {a,b}, I'm trying to find the generating function that distinguishes, for all words of fixed length $n$, the count of blocks of a's and the number of a's. Let $x^p$ count the ...
7
votes
1answer
372 views

Challenging recurrence relation problem

I am starting out with the following: $$ \frac{d^n}{dx^n}[g(x)^{f(x)}] = \sum_{c=0}^n g(x)^{f(x)-c}\lambda_{n,c}(x) $$ Therefore: $$ \frac{d^{n+1}}{dx^{n+1}}[g(x)^{f(x)}] = ...
7
votes
1answer
260 views

Compute limit of the sequence $x_n$ given by $x_{n+2}=-\frac{1}{2}(x_{n+1}-x_n^2)^2+x_n^4$

Let $(x_n)$ be a real sequence such that $x_0=a\in\mathbb{R},x_1=b\in\mathbb{R},x_{n+2}=-\dfrac{1}{2}\left(x_{n+1}-x_{n}^2\right)^2+x_{n}^4\;\forall n\in\mathbb{N} $ and $|x_n|\leq ...
7
votes
1answer
149 views

What are the solutions for $a(n)$ and $b(n)$ when $a(n+1)=a(n)b(n)$ and $b(n+1)=a(n)+b(n)$?

If you have the following recurrence relations : $a(n+1)= a(n) b(n)$ $b(n+1)= a(n) + b(n) $ How do you find the form of $a(n)$ and $b(n)$ ? I suspect there isn't a closed form , but a infinit sum ...
7
votes
2answers
148 views

How can I prove that this recursive sequence converges?

Let $a_0=1$, $a_1=1$ and $a_{n+2}=\frac{1}{a_{n+1}}+\frac{1}{a_n}$. How can I prove that this sequence is convergent? I know that if it's convergent, it converges to $\sqrt{2}$ and I can calculate the ...
7
votes
1answer
146 views

Nonlinear inhomogeneous recurrence $f(x)^2=f(x+1)+S(x)$ to find nested radical

I want to solve the recurrence relation $$f(x)^2=f(x+1)+S(x)$$ where $S(x)$ is a given polynomial. The background is to find nested radicals expressions of the form ...
7
votes
1answer
50 views

Recurrence $u_{n+1}u_{n-1}-u_n^2=Ar^{n-1}$

I was going through some old puzzles and encountered one where there was a non-linear recurrence of form $$u_{n+1}u_{n-1}-u_n^2=Ar^{n-1}$$ with $u_0$ and $u_1$ given. I know I can use a test form ...
7
votes
1answer
590 views

The Average Running Time Of Euclid Algorithm?

What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$? It seems very hard to deduce from the recurrence $T(m,n) = T(n, m ...
7
votes
1answer
603 views

Any serious work on Lychrel numbers/$196$-Algorithm?

I've been googling around a little lately and have stumbled across the so called Lychrel problem. For a natural number $x$, let $Rx$ denote the number obtained by reversing the base-$10$ digits of $x$ ...
7
votes
0answers
113 views

Is this a recurrence for the characteristic sequence of composite numbers?

The characteristic sequence of composite numbers is equal to 1 if $n$ is not a prime number and equal to 0 if $n$ is a prime number, starting: $$1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1,...$$ where the ...
7
votes
1answer
112 views

Another recurrence… $T(n)=\sqrt{2n} \cdot T(\sqrt{2n}) + \sqrt{n}$

I'm trying to solve the following recurrence : $$T(n)=\sqrt{2n}\cdot T(\sqrt{2n}) + \sqrt{n}$$ I've tried substituting $n$ for some other variables to transform the above to something easier without ...
7
votes
0answers
98 views

Properties of a continued fraction convolution operation

Usually the partial numerators of a continued fraction are all 1s. Has anyone considered the operation where you convolve 1 continued fraction with another, in other words, make a new continued ...
6
votes
4answers
383 views

How to solve this recurrence $K(n)=2K(n-1)-K(n-2)+C$?

The recurrence is $K(n)=2K(n-1)-K(n-2)+C$ where $C$ is a constant. What I have tried is substituting $2K(n-1)$ as we do in fibonnacical recurrences. It didn't gave me a fruitful expression! Can ...
6
votes
5answers
207 views

How can I find the value of $a^n+b^n$, given the value of $a+b$, $ab$, and $n$?

I have been given the value of $a+b$ , $ab$ and $n$. I've to calculate the value of $a^n+b^n$. How can I do it? I would like to find out a general solution. Because the value of $n$ , $a+b$ and $ab$ ...
6
votes
6answers
1k views

How to find the limit of this recurrence relation?

$a_n$ is a sequence where $a_1=0$ and $a_2=100$, and for $n \geq 2$: $$ a_{n+1}=a_n+\frac{a_n-1}{(n)^2-1} $$ I have a basic understanding of sequences. I wasn't sure how to deal with this recurrence ...
6
votes
2answers
2k views

Recursive square root problem [duplicate]

Give a precise meaning to evaluate the following: $$\large{\sqrt{1+\sqrt{1+\sqrt{1+\sqrt{1+\dotsb}}}}}$$ Since I think it has a recursive structure (does it?), I reduce the equation to $$ ...
6
votes
4answers
148 views

closed form for $d(4)=2$, $d(n+1)=d(n)+n-1$?

I am helping a friend in his last year of high school with his math class. They are studying recurrences and proof by inference. One of the exercises was simply "How many diagonals does a regular ...
6
votes
2answers
71 views

How to evaluate $\lim_{ n\to \infty }\frac{a_n}{2^{n-1}}$, if $a_0=0$ and $a_{n+1}=a_n+\sqrt{a_n^2+1}$?

Let $a_1,a_2,..,a_n$ be sequence of real numbers such that $a_{n+1}=a_{n}+\sqrt{1+a_n^2}$ and $a_0=0$. How to evaluate $\lim_{ n\to \infty }\frac{a_n}{2^{n-1}}$ ?
6
votes
2answers
389 views

A Recurrence Relation Involving a Square Root

Consider the recurrence relation: $a_{n+1} = \sqrt{a_n^2 -k},$ where $k>0$, $n\in\{0,1,n:a_n^2\geq k\}$, and $a_0>0$ is known. Is it possible to obtain an expression for $a_n$ in terms of ...
6
votes
5answers
153 views

$x_{n+1} = \sqrt{3x_n}$ converges for $x_1 = 1,x_1 = 27$ Proof

Prove $x_{n+1} = \sqrt{3x_n}$ converges for $x_1 = 1,x_1 = 27$. (Separate problems for $x_1 = 1$ and $x_1 = 27$.) EDIT: Took out bad algebra.
6
votes
2answers
217 views

Convergence of sequence: $f(n+1) = f(n) + \frac{f(n)^2}{n(n+1)}$

I am trying to work out a problem on some old analysis qual exam, and managed to reduce it to this question, but I can't seem to figure out this final step: Consider the sequence defined by the ...
6
votes
3answers
92 views

Please solve this recurrence relation question for $8a_na_{n+1}-16a_{n+1}+2a_n+5=0$

Suppose $a_1=1$ and $$8a_na_{n+1}-16a_{n+1}+2a_n+5=0,\forall n\geq1,$$Please help to sort out the general form of $a_n$. Here are the first a few values of the series. Not sure if they are useful as ...
6
votes
4answers
256 views

Alternating Recurrence relation $a_n = b_{n-1} + 5$ and $b_n = na_{n-1}$

I am racking my brain on solving the relation where: $$a_n = b_{n-1} + 5$$ $$b_n = na_{n-1}$$ where $a_0$ = $b_0$ = 1 I am trying to find the closed form for $a_n$. I have tried to shifting $b_n = ...