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

learn more… | top users | synonyms

6
votes
3answers
226 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 = ...
6
votes
4answers
190 views

Recursive Sequence Tree Problem (Original Research in the Field of Comp. Sci)

This question appears also in http://cstheory.stackexchange.com/questions/17953/recursive-sequence-tree-problem-original-research-in-the-field-of-comp-sci. I was told that cross-posting in this ...
6
votes
2answers
113 views

Finding non-negative integers $m$ such that $(1 + \sqrt{-2})^m$ has real part $\pm 1$.

I believe that the integers $m$ with $(1+\sqrt{-2})^m$ having real part $\pm 1$ are $0, 1, 2$ and $5$, but I'm having trouble proving it. Write $$a_m = \Re((1+\sqrt{-2})^m) = \frac{(1 + \sqrt{-2})^m ...
6
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, ...
6
votes
1answer
497 views

Solving a simple recurrence relation

I have the following recurrence relation: $a_0=1$ $a_{n}=pa_{n+1}+qa_{n-1}$ Where $p+q=1$. This relation arises in analyzing a "gambler's ruin" situation. It is claimed that the general solution ...
6
votes
2answers
420 views

Convergence/Divergence of a particular infinite nested radical

Is it known if the following infinite nested radical converges or diverges (for $n \in \mathbb N$)?: $$R(n) = \sqrt{n+\sqrt{(n+1)+\sqrt{(n+2)+ \cdots}}}$$ I recently became interested in these ...
6
votes
4answers
503 views

How to find limit of a sequence defined by recurrence formula

I have the following problem: Let $a_{n}$ be the recurrence $$a_{n+1}=a_{n}+2a_{n-1}$$ with $a_{0}=0$ and $a_{1}=1$. Can you help me find $$\lim_{n\to\infty} \frac{a_{n+1}}{a_{n}}$$ for $n\geq ...
6
votes
1answer
3k views

Find a big-O estimate for $f(n)=2f(\sqrt{n})+\log n$

While self-studying Discrete Mathematics, I found the following question in the book "Discrete Mathematics and Its Applications" from Rosen: Suppose the function $f$ satisfies the recurrence ...
6
votes
2answers
836 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 ...
6
votes
2answers
112 views

$a_1=1,a_{n+1}=\frac{n}{a_n}+\frac{a_n}{n}$. Prove that for $n\ge4$, $\lfloor{a_n^2}\rfloor=n$

Define a sequence $\left\lbrace a_{n}\right\rbrace$ by $\displaystyle{a_{1} = 1\,,\ a_{n + 1} = {n \over a_n} + {a_n \over n}.\quad}$ Prove that for $n \geq 4,\,\,\left\lfloor ...
6
votes
1answer
306 views

Recurrence relation telescoping

Hi there I am trying to solve the following recurrence relation using telescoping. How would I go about doing it? $$T(n) = \frac 2n \Big(T(0) + T(1) + \ldots+ T(n-1)\Big) + 5n$$ Assuming $n\ge 1$
6
votes
1answer
103 views

How to prove that this recursively defined sequence converges to $e$?

Let $a_1=0,a_2=1,$ and $a_{n+2}=\dfrac{(n+2) a_{n+1}-a_n}{n+1}$. Prove that $\lim_{n\to \infty}a_n=e$. I know that $\lim_{n\to\infty}\left(1+\frac1{2!}+\frac1{3!}+...+\frac1{n!}\right)=e$ and $a_n = ...
6
votes
2answers
133 views

Generating Functions: Solving a Second-Order Recurrence

I'm self-studying generating functions (using GeneratingFunctionology as a text). I came across this programming problem, which I immediately recognized as a modification of the Fibonacci sequence. ...
6
votes
1answer
322 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: ...
6
votes
1answer
125 views

Limit related to the recursion $a_{n+1}=(1-n^{-1/4}a_n)a_n$

Let $0<a_{1}<1$, with $$a_{n+1}=a_{n}(1-n^{-\frac{1}{4}}a_{n})$$ Does there a real numbers $A$ which make the limit $$ ...
6
votes
2answers
147 views

The limit of a recurrence relation (with resistors)

Background to problem (not too important): My proposed solution: The infinitely long element, , however complex, can be represented as a single resistor of resistance $R$. Remembering the ...
6
votes
1answer
239 views

Finding ($2012$th term of the sequence) $\pmod {2012}$

Let $a_n$ be a sequence given by formula: $a_1=1\\a_2=2012\\a_{n+2}=a_{n+1}+a_{n}$ find the value: $a_{2012}\pmod{2012}$ So, in fact, we have to find the value of ...
6
votes
2answers
89 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, ...
6
votes
1answer
130 views

How find $a_{n}$ if $a_{n+1}=\sqrt{2a_n+1}$

let $a_{1}=\dfrac{\sqrt{2}}{4}$ and such $$a_{n+1}=\sqrt{2a_{n}+1}$$ find $a_{n}$ my idea:let $a_{n}=\dfrac{1}{2}\cos{x_{n}}$ $$\Longrightarrow ...
6
votes
1answer
185 views

Line in a proof on p69 in Cassel's Local Fields

I'm trying to read the proof of LEMMA 6.1 (Nagell) Let $u_n$ be defined by $u_0=0$, $u_1=1$ and $u_n=u_{n-1}-2u_{n-2} \hspace{20pt} (n\geq 2)$. Then $u_n=\pm1$ only for $n=1,2,3, ...
6
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 ...
6
votes
1answer
267 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 ...
6
votes
1answer
259 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 ...
6
votes
2answers
364 views

How to prove $\lim_{n\to\infty}\frac{\log_{2}{(f_{n})}}{(\log_{2}{n})^2}=\frac{1}{2}$?

For any $n\in N$, such $f_{1}=1$, and such $$f_{2n+1}=f_{2n}=f_{2n-1}+f_{n},$$ prove that $$\lim_{n\to\infty}\dfrac{\log_{2}{(f_{n})}}{(\log_{2}{n})^2}=\dfrac{1}{2}.$$
6
votes
1answer
140 views

Recurrence Relation

How do I solve: $k(k+1)a_{k}=2(\lambda k-1)a_{k-1}+(a-\lambda^2)a_{k-2}$ where $\lambda$ and $a$ are constants, and similar other recurrence relations?
6
votes
2answers
328 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 ...
6
votes
1answer
150 views

Prove that every element of $a_{n+2013}=\frac{a_{n+1}a_{n+2}…a_{n+2012}+1}{a_n}$ is an integer

Given $\displaystyle a_1=a_2=\cdots=a_{2013}=1$ and $\displaystyle a_{n+2013}=\frac{a_{n+1}a_{n+2}\cdots a_{n+2012}+1}{a_n}$. Prove that $a_{n+2013}\in\mathbb{N}$ for all $n\in\mathbb{N}$. I ...
6
votes
0answers
89 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 ...
6
votes
0answers
40 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 ...
6
votes
0answers
157 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 ...
5
votes
5answers
257 views

Prove that the sequence with $T(0)=1$ and $T(n) = 1 + \sum_{j=0}^{n-1}T(j)$ is given by $T(n)=2^n$

$T(0)=1 \\ T(n) = 1 + \sum_{j=0}^{n-1}T(j) \\ $ Show that $T(n) = 2^n$. I know how to prove this by induction, but I would like to know how to show this using first principles. Edit: The way I want ...
5
votes
4answers
304 views

General expression of $f(a, b)$ if $f(a, b)=f(a-1,b) + f(a, b-1) + f(a-1, b-1)$?

$f(a,b) = f(a-1, b) + f(a-1, b-1) + f(a, b-1), ab \neq 0$ $f(a,b) = 1, ab = 0$ So what is $f(a, b)$?
5
votes
4answers
406 views

What explains this bizarre behavior?

Consider the sequence $x_{n+1} = 2x_{n}-\frac{1}{x_n},n\geq0 $. For $x_{0} = 0,87$ we have $$ \begin{aligned} X(1) &\approx 0,590574712643678 \\ X(2) &\approx -0,512116436915835\\ X(3) ...
5
votes
3answers
353 views

Determining if a recursively defined sequence converges and finding its limit

Define $\lbrace x_n \rbrace$ by $$x_1=1, x_2=3; x_{n+2}=\frac{x_{n+1}+2x_{n}}{3} \text{if} \, n\ge 1$$ The instructions are to determine if this sequence exists and to find the limit if it exists. I ...
5
votes
5answers
98 views

Recurrence of the form $2f(n) = f(n+1)+f(n-1)+3$

Can anyone suggest a shortcut to solving recurrences of the form, for example: $2f(n) = f(n+1)+f(n-1)+3$, with $f(1)=f(-1)=0$ Sure, the homogenous solution can be solved by looking at the ...
5
votes
2answers
194 views

Dynamics of the repetitions of $f(z) = z^{2} +\frac{1}{4}$

This is probably a classic and most likely an easy question, but I was not able to find an answer. If we have the iteration $z_{n+1}=g(z_n)$, where $$g(z) = z + a z^{2},$$ with $a\ne 0$, then using a ...
5
votes
3answers
360 views

How to solve this recurrence using generating functions?

Exercise: For $n \geq 0$ let $a_n = \sum \limits_{i=0}^n (i^2- 2i + 1)$ a) Show that $$a_{n+4} -4a_{n+3} + 6a_{n+2} - 4a_{n+1} + a_n = 0, n \geq 0$$ b) Identify the genereating series ...
5
votes
1answer
185 views

How to solve this recurrence relation $a_{n+2} = \sqrt{a_{n+1}\cdot a_{n}}$?

I am trying to solve the recurrence: $$ a_{n+2} = \sqrt{a_{n+1}\cdot a_{n}} $$ but here is a problem for me. After few steps I have this: $$ a_n^2 = a_{n-1}\cdot a_{n-2} $$ and I don't now what to do ...
5
votes
3answers
753 views

Analysis of Algorithms: Solving Recursion equations-$T(n)=3T(n-2)+9$

I need your help with solving this recursion equation: $T(n)=3T(n-2)+9$. with the initial condition : $T(1)=T(2)=1$. I need to find $T(n)$, the complexity of the algorithm which works that way. I ...
5
votes
2answers
267 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 ...
5
votes
5answers
340 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 ...
5
votes
5answers
745 views

Solving a set of recurrence relations

I have the 7 following reccurence relations: $A_n = B_{n-1} + C_{n-1}$ $B_n = A_n + C_{n-1}$ $C_n = B_n + C_{n-1}$ $D_n = E_{n-1} + G_{n-1}$ $E_n = D_n + F_{n-1}$ $F_n = G_n + C_n$ $G_n = E_n + ...
5
votes
5answers
312 views

What particular solution should I guess for this relation?

Just trying to solve a non-homogeneous recurrence relation: $$f(n) = 2f(n-1) + n2^n$$ $$f(0) = 3$$ Characteristic equation is: $$f(n) - 2f(n-1) = 0$$ $$a-2 = 0$$ $$a = 2$$ Homogeneous ...
5
votes
1answer
152 views

Solve a recurrence relation $D_{n} = nD_{n-1} + (n-1)!$

As the title states, I need a solution of this recurrence but I'll provide my own solution and ask if there is an easier, simpler solution using some deeper knowledge about recurrence relations. ...
5
votes
3answers
132 views

Prove that this recurrence always cycles

If $n$ is a nonnegative integer, let $S_n=\{0, 1, 2, \dots, 2n+1\}$. For $t\in S_n$ repeatedly perform if t is even t = t/2 else t = (n + 1 + ⌊t/2⌋) ...
5
votes
3answers
83 views

sequence $U_k=a_0U_{k-1}+a_1U_{k-2}+\cdots+a_{k-1}U_0$

Is there a general formula for $U_k$ defined by $$U_k=a_0U_{k-1}+a_1U_{k-2}+\cdots+a_{k-1}U_0$$ where the $a_i$ are in arithmetic progression and $U_0=1$? Do there always exist $c,d$ such that ...
5
votes
1answer
158 views

Strange Recurrence: What is it asymptotic to?

So I have the following recurrence relation for the growth rate of an algorithm: $T(n)$ = time taken by algorithm to solve problem of size n: $$T(n) = T(n-1) + T(\lceil(n/2)\rceil)$$ Clearly this ...
5
votes
2answers
205 views

Combinatorial explanation to following recurrence relation $a_n = 2 a_{n-1} + a_{n-2}$

Question was the following: $a_n$ is the number of ternary strings (strings of 0,1,2) which contain no consecutive zeros and no consecutive ones. Find a formula for $a_n$? By brute force, I found a ...
5
votes
4answers
189 views

Finding the general term of two related recurrence relations

I'm trying to find the general term of the recurrence relations $\quad a_{n+1}=a_n+\text hb_n$ $\quad b_{n+1}=b_n-\text ha_n $ $\quad a_0=0, \quad b_0=1$ I tried finding the terms, ...
5
votes
3answers
940 views

How to solve this recurrence relation

What are some ways to solve this recurrence relation: $a(n+1)=2 a(n) - a(n-1) -1, \text{ with }a(0)=0, a(10)=0?$ I tried to first convert this inhomogeneous equation into a homogeneous one following ...