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

learn more… | top users | synonyms (2)

13
votes
3answers
401 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 ...
13
votes
3answers
1k views

Recursive Integration over Piecewise Polynomials: Closed form?

Is there a closed form to the following recursive integration? $$ f_0(x) = \begin{cases} 1/2 & |x|<1 \\ 0 & |x|\geq1 \end{cases} \\ f_n(x) = 2\int_{-1}^x(f_{n-1}(2t+1)-f_{n-1}(2t-1))\mathrm{...
13
votes
2answers
3k views

Evaluating the limit of a sequence given by recurrence relation $a_1=\sqrt2$, $a_{n+1}=\sqrt{2+a_n}$. Is my solution correct?

Problem The sequence $(a_n)_{n=1}^\infty$ is given by recurrence relation: $a_1=\sqrt2$, $a_{n+1}=\sqrt{2+a_n}$. Evaluate the limit $\lim_{n\to\infty} a_n$. Solution Show that the sequence $(...
13
votes
1answer
399 views

Why do the Fibonacci numbers recycle these formulas?

The Fibonacci numbers $F_n = 0, 1, 1, 2, 3, 5, 8, 13, \dots$ obey the following recurrence relations, $ \begin{aligned} &F_{n}-\;F_{n-1}-F_{n-2} = 0\\[1.5mm] &F_{n-1}^3-F_{n}^3-F_{n+1}^3 = -...
13
votes
1answer
7k views

Odd and even numbers in Pascal's triangle-Sierpinski's triangle

Moderator Note: At the time that this question was posted, it was from an ongoing contest. The relevant deadline has now passed. I recently learned that when the Pascal's triangle is reduced to ...
13
votes
1answer
313 views

Convergence of the quadratic map $\left(x-\left(x-\left(x- \dots \right)^2 \right)^2 \right)^2$?

Edit - I changed the title and much of the body to better reflect my full question. The old one I don't really care about, although I appreciate Fabian's answer of course. Here is the plot for the ...
13
votes
2answers
604 views

Zeroes of the third derivative of an iterated sine.

I've been playing with the functions $$f_n:[0,\pi/2]\to[0,1]\\\begin{cases} f_1&=&\sin\\f_{n+1}&=&\sin\circ f_n\end{cases}.$$ A simple argument proves that $f_n(x)\to 0$ for $x\in [0,\...
13
votes
1answer
2k views

Repertoire Method Clarification Required ( Concrete Mathematics )

In the book Concrete Mathematics, chapter 2, section 2.2 -- sums and recurrences, page 26 (2nd edition), the authors talk about the following example: Given the general recurrence $$ R(0) = \alpha $$...
13
votes
1answer
247 views

Integer Sequence “sums of digits of squares”.

For all $n \in \mathbb{N}$ we define the function $\delta(n)=p$, where $p$ is sums of digits of $n^2$. For example if $n=17, \ n^2=289$, then $\delta(17)=2+8+9=19$. Let $a_k$ is a monotonically ...
13
votes
2answers
2k views

Exact probability of random graph being connected

The problem: I'm trying to find the probability of a random undirected graph being connected. I'm using the model $G(n,p)$, where there are at most $n(n-1) \over 2$ edges (no self-loops or duplicate ...
12
votes
3answers
6k 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., $[x]$...
12
votes
3answers
5k views

Why is solving non-linear recurrence relations “hopeless”?

I came across a non-linear recurrence relation I want to solve, and most of the places I look for help will say things like "it's hopeless to solve non-linear recurrence relations in general." Is ...
12
votes
2answers
444 views

Finding the limits

Suppose $a_1=1, a_{k+1}=\sqrt{a_1+a_2+\cdots +a_k}, k \in \mathbb{N}$. Find the limits $$i)\space \lim_{n\to\infty}\displaystyle \frac{\sum_{k=1}^{n} a_{k}}{n\sqrt{n}}$$ $$ii)\space \lim_{n\to\infty}\...
12
votes
3answers
9k views

Links between difference and differential equations?

Does there exist any correspondence between difference equations and differential equations? In particular, can one cast some classes of ODEs into difference equations or vice versa?
12
votes
1answer
210 views

Family of GCDs all equal to $2$

Is it true that $$\gcd\left(5^{2^n} + 1, 13^{2^n} + 1\right) = 2$$ for all $n \in \mathbf{Z}_{\geq 0}$? I'm continually stumped with this and verifying it numerically is quite expensive very ...
12
votes
1answer
234 views

A series: $1-\frac{1}{2}-\frac{1}{3}-\frac{1}{4}+\frac{1}{5}-\frac{1}{6}+\frac{1}{7}+\cdots$

Denote $$b_1=1,b_{n}=b_{n-1}-\dfrac{S(b_{n-1})}{n},(n>1 )\tag1$$ where $S(x)=1$ if $x>0,S(x)=-1$ if $x<0$, and $S(0)=0.$ So $b_n=1,\dfrac{1}{2},\dfrac{1}{6},-\dfrac{1}{12},\dfrac{7}{60},-\...
12
votes
3answers
310 views

How to find a “better description” (e.g. recurrence relation) for this sequence?

My solution to a problem in Project Euler required to solve this subproblem: find values of $k\in\mathrm{N}$ such that $3k^2+4$ is a perfect square. As I was writing a computer program, I just tried ...
11
votes
4answers
786 views

How to find explicit formula for two recursions?

I have to find explicit solution for two intertwining recursions $$\begin{align} f(n)&=f(n-2)+2g(n-1) \\ g(n)&=g(n-2)+f(n-1) \end{align}$$ for $f(0)=1, f(1)=0, g(0)=0 ,g(1)=1$. What ...
11
votes
4answers
2k views

Exponential growth of cow populations in Minecraft

Minecraft is a computer game where you can do many things including farm cows. When fed wheat, cows in Minecraft breed with each other in pairs and produce one baby per pair. After about 20 minutes ...
11
votes
5answers
1k views

How to deduce a closed formula given an equivalent recursive one?

I know how to prove that a closed formula is equivalent to a recursive one with induction, but what about ways of deducing the closed form initially? For example: $$ f(n) = 2 f(n-1) + 1 $$ I know ...
11
votes
3answers
2k views

Stirling number of the first kind: Proof of Recursion formula

I want to prove this recursion formula for Stirling numbers of the first kind: $$s_{n+1,k+1} = \sum_{i=k}^{n} \binom{i}{k} s_{n,i}$$ But I lack a useful idea. Perhaps someone could inspire me? ...
11
votes
3answers
395 views

Difficult Recurrence

I am trying to solve a Sangaku problem. The blue circles have radii one. The goal is to find the total area of all the other circles (the three sequences of circles repeat ad infinitum). I have ...
11
votes
3answers
96 views

Recursive Sequence $a_n = \frac{1}{2} (a_{n-1} + 5) $

I got this question in which they ask me to explain why it is convergent and evaluate its limit. $$a_1=3\;and\;a_n = \frac{1}{2} (a_{n-1} + 5) \\ n=2,3,4,... $$ To prove it's convergent, I show ...
11
votes
1answer
264 views

Mathematics of the Ice Bucket Challenge

I've been considering the mathematics of the now global ice bucket challenge. Simple model In the simplest incarnation, there is one original seed, who then nominates 3 others, each of which take ...
10
votes
5answers
3k views

Proof of Convergence: Babylonian Method $x_{n+1}=\frac{1}{2}(x_n + \frac{a}{x_n})$

a) Let $a>0$ and the sequence $x_n$ fulfills $x_1>0$ and $x_{n+1}=\frac{1}{2}(x_n + \frac{a}{x_n})$ for $n \in \mathbb N$. Show that $x_n \rightarrow \sqrt a$ when $n\rightarrow \infty$. I have ...
10
votes
4answers
4k views

Interesting properties of Fibonacci-like sequences?

Everyone is familiar with the Fibonacci Sequence, [0] 1 1 2 3 5 8 ... and many of it's interesting properties. For example, as the sequence continues, the ratio of $...
10
votes
2answers
2k views

Linear homogeneous recurrence relations with repeated roots; motivation behind looking for solutions of the form $nx^n$?

If we have a linear homogeneous recurrence relation, such as $t_{k+1}=4t_k-4t_{k-1}$, and attempt to find solutions of the form $t_n=x^n$ for some $x \in \mathbb{R} \setminus \{0\}$, we obtain the ...
10
votes
3answers
195 views

Show that $2^n(\cos^n(\frac{2\pi}{9})+\cos^n(\frac{4\pi}{9})+\cos^n(\frac{8\pi}{9}))\in\mathbb{Z}$

$a_n=2^n\left[\cos^n\left(\dfrac{2\pi}{9}\right)+\cos^n\left(\dfrac{4\pi}{9}\right)+\cos^n\left(\dfrac{8\pi}{9}\right)\right]$. Show that $a_n\in\mathbb{Z}$ for all $n\in\mathbb{Z}$. Find the last ...
10
votes
1answer
383 views

Prove that this particular sequence contains an infinite number of sixes

Given the sequence $$2,7,1,4,7,4,2,8,\ldots$$ which begins with $2, 7$ and is constructed by multiplying successive pairs of its members and adjoining the results as the next one or two members of ...
10
votes
1answer
152 views

Find asymptotic of recurrence sequence

Given a sequence $x_1=\frac{1}{2}$, $x_{n+1}=x_n-x_n^2$. It's easy to see that it limits to $0$. The question is: is there exists an $\alpha$ such, that $\lim\limits_{n\to\infty}n^\alpha x_n\neq0$. ...
10
votes
4answers
8k views

What is the solution to the following recurrence relation with square root: $T(n)=T (\sqrt{n}) + 1$?

This looks like a question asked earlier, but it isn't. $$T(n)=\begin{cases} T (\sqrt{n}) + 1 \quad & \text{ if } n>1 \\ 1 & \text{ if }n=1\end{cases}$$ My professor gave this to me in ...
10
votes
2answers
397 views

How many permutations of a multiset have a run of length k?

Background $\newcommand\ms[1]{\mathsf #1}\def\msP{\ms P}\def\msS{\ms S}\def\mfS{\mathfrak S}$Suppose I have $n$ marbles of $c$ colors, where $c≤n$. Let $n_i$ denote the number of marbles of color $i$....
10
votes
1answer
416 views

Closed form for $a_{n+1} = (a_n)^2+\frac{1}{4}$

I've been given the following sequence: \begin{align*} &a_0 = 0; \\ &a_{n+1} = (a_n)^2+\frac{1}{4}. \end{align*} I also have to prove that whatever I come up with is correct, but that will ...
10
votes
3answers
439 views

Solving randomized recurrence relation

I'm looking at the random sequence $x_n$ with $x_0=x_1=1$ and \begin{equation} x_{n+1}=2x_n\pm x_{n-1} \end{equation} where we choose the $\pm$ sign independently with equal probability. Now ...
10
votes
3answers
273 views

Is the sequence defined by the recurrence $a_{n+2}=\frac{1}{a_{n+1}}+\frac{1}{a_n}$ convergent?

Let $a_0=1$, $a_1=1$ and $a_{n+2}=\frac1{a_{n+1}}+\frac1{a_n}$ for every natural number $n$. How can I prove that this sequence is convergent? I know that if it's convergent, it converges to $\...
10
votes
1answer
251 views

Does this functional equation have a non-trivial closed form solution?

$$P(c \cdot x) = \cos(x) P(x)$$ For $c=2$, $P(x) = \sin(x)/x$ is a solution to this. I don't know if there's a closed-form solution for $c \ne 2$. Rather than add my own attempt at solution, which ...
10
votes
2answers
149 views

Does equation $f(g(x))=a f(x)$ have a solution?

Suppose $g: [0,1] \to [0,1]$ is a strictly increasing, continuously differentiable function with $g(0)=0$ and $g(1) < 1$, and $a \in (0,1)$. Is there a function $f:[0,1] \to \mathbb{R}$ such that $...
10
votes
1answer
1k views

How to solve non-linear recurrence relation in general?

For linear recurrence, we can use generating function. So is there a general technique to solve non-linear recurrence or it depends on a specific sequence? For example, $$a_{n+1} = \dfrac{a_n(a_n - 3)}...
10
votes
1answer
328 views

Using Dyson's conjecture to give another proof of Dixon's identity.

For natural numbers $a_1,\dots,a_n$, Freeman Dyson conjectured (and it was eventually proven) that the Laurent polynomial $$ \prod_{i,j=1\atop i\neq j}^n\left(1-\frac{x_i}{x_j}\right)^{a_i} $$ has ...
10
votes
1answer
231 views

Solve $A_n=A_{n-1}+\lfloor \sqrt{A_{n-1}}\rfloor$

I am trying to solve the recurrence: $A_0=1$ $A_n=A_{n-1}+\lfloor \sqrt{A_{n-1}}\rfloor,\text{ for } n > 0$ Its obvious that $A_n=m^2 \implies A_{n+1}=m^2+m$ however my book's solution states ...
10
votes
0answers
186 views

Recurrence relations with multiple roots of auxiliary equation

Suppose we have a homogeneous linear recurrence relation of the form $$u_{n+r}+a_1u_{n+r-1}+\dots +a_ru_n=0$$ The auxiliary equation is then $$f(x)=x^r+a_1x^{r-1}+\dots +a_r=0$$ It is well known that ...
9
votes
8answers
292 views

Proof that if $a_1=1$ and $a_{n+1}=1+\frac{1}{1+a_n}$

Question: Proof that if $$a_n=\left\{ \begin{array}{ll} a_1=1\\ a_{n+1}=1+\frac{1}{1+a_n} \end{array} \right.$$ then $a_n$ converge, and then find $\lim_{n \to \infty}a_n$. I found ...
9
votes
3answers
426 views

Solving the recurrence relation $A_n=n!+\sum_{i=1}^n{n\choose i}A_{n-i}$

I am attempting to solve the recurrence relation $A_n=n!+\sum_{i=1}^n{n\choose i}A_{n-i}$ with the initial condition $A_0=1$. By "solving" I mean finding an efficient way of computing $A_n$ for ...
9
votes
3answers
838 views

Obtaining binomial coefficients without “counting subsets” argument

I want to obtain the formula for binomial coefficients in the following way: elementary ring theory shows that $(X+1)^n\in\mathbb Z[X]$ is a degree $n$ polynomial, for all $n\geq0$, so we can write $$...
9
votes
1answer
723 views

Recurrence for the partition numbers

I'm reading Analytic Combinatorics [PDF] book by Flajolet and Sedgewick, and I can't figure out one of the steps in the derivation of the $P_n$ — number of partitions of size $n$ (or coefficients in ...
9
votes
4answers
157 views

Prove the series has positive integer coefficients

How can I show that the Maclaurin series for $$ \mu(x) = (x^4+12x^3+14x^2-12x+1)^{-1/4} \\ = 1+3\,x+19\,{x}^{2}+147\,{x}^{3}+1251\,{x}^{4}+11193\,{x}^{5}+103279\, {x}^{6}+973167\,{x}^{7}+9311071\,{x}^{...
9
votes
2answers
105 views

Proving that $a_n$ is an integer for every $n$

For every $k\ge1$ integer number if we define the sequence : $a_1,a_2,a_3,...,$ in the form of :$$a_1=2$$ $$a_{n+1}=ka_n+\sqrt{(k^2-1)(a^2_n-4)}$$ For every $n=1,2,3,....$ how to prove that $a_n$ is ...
9
votes
2answers
630 views

A polynomial sequence

I have a sequence of polynomials $Q_k(x, y)$, $k\geq 1$ defined recursively as follows: $Q_1=x$. There is a sequence of polynomials $p_j(y)$ of degree $j$ such that $Q_{2m}$ is of the form \begin{...
9
votes
1answer
300 views

What is a good asymptotic for $f_n = f_{n-1}+\ln(f_{n-1})$?

Let $f_0=2$ and $f_n=f_{n-1}+\ln(f_{n-1})$. What is a good asymptotic to the sequence $f_n$? With good I mean much better than $f_n \sim \dfrac{3n \ln(2)\ln(n)}{2}$.
9
votes
1answer
330 views

Möbius function from random number sequence

Consider some arbitrary number sequence like the decimal expansion of $\pi$ = {3, 1, 4, 1, 5, 9, 2}. Prepend the sequence with the number $1$ so that you get {1, 3, 1, 4, 1, 5, 9, 2}. Then plug it ...