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

learn more… | top users | synonyms (2)

11
votes
5answers
855 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
286 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
2answers
2k 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
3answers
822 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
4answers
3k 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
186 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
129 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
203 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
766 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
279 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
381 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
328 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
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 ...
9
votes
3answers
493 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
490 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
372 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
271 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
271 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
269 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
286 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
292 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
322 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
2answers
591 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
591 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
544 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
152 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
2answers
79 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
421 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
90 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
965 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
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 ...
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
509 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
81 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
227 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
309 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
391 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
381 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
327 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
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
317 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$.