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

learn more… | top users | synonyms (2)

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 ...
13
votes
2answers
602 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 ...
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
244 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., ...
12
votes
2answers
441 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 ...
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
208 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
233 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 ...
12
votes
3answers
304 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
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 ...
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
389 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 ...
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
1answer
151 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
7k 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
389 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 ...
10
votes
1answer
411 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
437 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
266 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
2answers
147 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 - ...
10
votes
1answer
325 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
229 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
239 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
0answers
180 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
423 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
192 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 ...
9
votes
1answer
380 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 ...
9
votes
3answers
818 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
714 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
153 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\, ...
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
626 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 ...
9
votes
1answer
299 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
327 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 ...
9
votes
4answers
506 views

Help with a recurrence with even and odd terms [duplicate]

I have the following recurrence that I've been pounding on: $$ a(0)=1\\ a(1)=1\\ a(2)=2\\ a(2n)=a(n)+a(n+1)+n\ \ \ (\forall n>1)\\ a(2n+1)=a(n)+a(n-1)+1\ \ \ (\forall n\ge 1) $$ I don't have much ...
9
votes
1answer
380 views

How does one prove that $\zeta(3)$ is irrational?

How does one prove that $\zeta(3)$ is irrational ? I would like to know how Apery did it. In particular how a recursion gives rise to irrationality !?
9
votes
1answer
248 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 ...
9
votes
3answers
303 views

The integer $c_n$ in $(1+4\sqrt[3]2-4\sqrt[3]4)^n=a_n+b_n\sqrt[3]2+c_n\sqrt[3]4$

For non-negative integer $n$, write $$(1+4\sqrt[3]2-4\sqrt[3]4)^n=a_n+b_n\sqrt[3]2+c_n\sqrt[3]4$$ where $a_n,b_n,c_n$ are integers. For any non-negative integer $m$, prove or disprove ...
9
votes
1answer
338 views

Recurrence equation similar to a geometric progression

I have the following recurrence relation: $$T(i) = \sqrt{T(i-1) \left(T(i+1) + k\right)},$$ with $k \geq 0$, a fixed constant. I know that when $k=0$, we have: $$T(i) = \sqrt{T(i-1) T(i+1)},$$ which ...
9
votes
1answer
66 views

Prime Concatenation Order

Consider the following procedure. Given an integer $n \geq 2$, obtain the canonical prime factorization of $n$, i.e. $\prod_{i=1}^k p_i^{e_i}$. Take the distinct factors $p_i$ and list them in ...
9
votes
0answers
263 views

Coefficients in expansion of $(\sqrt[3]{2} - 1)^m$

In trying to solve $a^3 - 2b^3 = 1$ over the integers I came across the need to answer the question: when does $(1+ \sqrt[3]{2} + \sqrt[3]{2}^2)^n$ have no $\sqrt[3]{2}^2$ term in it's expansion (in ...
9
votes
0answers
128 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 ...