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

learn more… | top users | synonyms (2)

11
votes
4answers
1k 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
876 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
6k 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?
11
votes
3answers
289 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
3answers
1k 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? ...
10
votes
3answers
834 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) = ...
10
votes
2answers
1k 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 ...
10
votes
4answers
2k 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
3answers
188 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
130 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
1answer
1k 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 ...
10
votes
3answers
423 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
1answer
308 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
206 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
1answer
786 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 - ...
9
votes
8answers
280 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
389 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
1answer
331 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
2answers
1k 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 ...
9
votes
3answers
531 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
519 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
2answers
100 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
1answer
375 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 ...
9
votes
1answer
272 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
2answers
285 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 ...
9
votes
4answers
297 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
291 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
3answers
293 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
326 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 ...
8
votes
4answers
4k views

How to find the closed form formula for this recurrence relation

$ x_{0} = 5 $ $ x_{n} = 2x_{n-1} + 9(5^{n-1})$ I have computed: $x_{0} = 5, x_{1} = 19, x_{2} = 83, x_{3} = 391, x_{4} = 1907$, but cannot see any pattern for the general $n^{th}$ term.
8
votes
3answers
3k 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 ...
8
votes
3answers
1k views

Solving a Recurrence Relation/Equation, is there more than 1 way to solve this?

1) Solve the recurrence relation $$T(n)=\begin{cases} 2T(n-1)+1,&\text{if }n>1\\ 1,&\text{if }n=1\;. \end{cases}$$ 2) Name a problem that also has such a recurrence relation. The ...
8
votes
2answers
602 views

Solving recurrence relations that involve all previous terms

I'm not sure if this a proper recurance relation per se but I'd be interested in the methodology in solving a recurrence relation of the following form: $Z_0 = 1$ $Z_1 = x_1$ $Z_2 = x_1Z_1 + x_2 = ...
8
votes
2answers
597 views

Reduction formula for $I_{n}=\int {\cos{nx} \over \cos{x}}\rm{d}x$

What would be a simple method to compute a reduction formula for the following? $\displaystyle I_{n}=\int {\cos{nx} \over \cos{x}} \rm{d}x~$ where $n$ is a positive integer I understand that it ...
8
votes
4answers
554 views

Closed form for a non-linear recurrence

Does equation $a_n=\sqrt{a_{n-1}+6}$ with $a_1=6$ have a closed form? I've found no linearization method. Any suggestion or hint will be highly appreciated.
8
votes
1answer
161 views

Find the general term of the sequence defined by $x_0 = 3, x_1 = 4$ and $x_{n+1} = x_{n-1}^2 - nx_n$

Question: Find the general term of the sequence defined by $x_0 = 3, x_1 = 4$ and $x_{n+1} = x_{n-1}^2 - nx_n$. Attempt: If I'm not mistaken this does not match any linear homogeneous pattern, nor ...
8
votes
1answer
132 views

Prove that a holonomic (p-recursive) difference equation returns only integral values

Consider the recurrence given by $(n+1)^2 a_{n+1} = (9n^2+9n+3)a_n-27n^2 a_{n-1}$ $a_0 = 1, a_1 = 3$. Clearly, $a_n$ is rational, but unexpectedly, the recurrence seems to output only integral ...
8
votes
1answer
95 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 ...
8
votes
2answers
84 views

Closed form of a recursive relation

A sequence $\langle a_n\rangle$ is defined recursively by $a_1=0$, $a_2=1$ and for $n\ge 3$, $$a_n=\frac 12 na_{n-1}+\frac 12n(n-1)a_{n-2}+(-1)^n\left(1-\frac n2\right).$$ Find a closed form ...
8
votes
1answer
422 views

How to solve this recurrence

Solve the recurrence \[ f_{j,k}^{(l)} = \begin{cases} \left[j>k\right] j^{k-1}(j-k), &\qquad j=l \\ \\ \left[j>k+1\right] \sum_t \binom k t f_{j-1,k-t}^{(l)}, &\qquad j>l \end{cases} ...
8
votes
0answers
107 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 ...
7
votes
8answers
974 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
398 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
538 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
1answer
84 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).$$ Then this problem says that $x_n\to\sqrt{a}$ as $n\to\infty.$ ...
7
votes
2answers
236 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
310 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
394 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
390 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
339 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 ...