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

learn more… | top users | synonyms (2)

7
votes
3answers
395 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
343 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
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, ...
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
331 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$.
7
votes
3answers
129 views

Help me understanding logic behind limits of recurence relations

I was trying to understand how limits of recurence relations are working. I have one. $$a_0 = \dfrac32 ,\ a_{n+1} = \frac{3}{4-a_n} $$ So, from what i know, if this recurence relation has a limit, ...
7
votes
1answer
231 views

Finding $a_n$ for very large $n$ where $a_n = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3} $

I have a recurrence relation, $$ a_n = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3} $$ for $n>3$ and $a_1 = 0, a_2 = 0, a_3 = 1$ I have to find the value of $a_n$ for very large values of n. I tried ...
7
votes
2answers
1k 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 ...
7
votes
1answer
354 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: ...
7
votes
3answers
436 views

Repertoire method for solving recursions

I am trying to solve this four parameter recurrence from exercise 1.16 in Concrete Mathematics: \[ g(1)=\alpha \] \[ g(2n+j)=3g(n)+\gamma n+\beta_j \] \[ \mbox{for}\ j=0,1\ \mbox{and}\ n\geq1 \] I ...
7
votes
1answer
339 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 ...
7
votes
3answers
1k views

Solving recurrence relation of form $T(n/2 + c)$

It is obvious that the Master Theorem cannot be applied to the recurrences of the following form: $T(n) = 4T(n/2 + 2) + n$ Since I am only interested in the $\theta$ bound of the recurrence and not ...
7
votes
1answer
132 views

Put a mouse to the last cell

We have (n=12) cells $C_1, C_2 ,\dots, C_{12}$ which are initially empty. At each step, we can do one of two operations: $\mathbf{P}$: Put only in the first cell $C_1$ 2 mice. $\mathbf{M}$: Move ...
7
votes
2answers
301 views

q-Analogue of the formula $x^n=\sum_k\left\{n\atop k\right\}(x)_k$.

The stirling numbers of the second kind satisfy the formula $x^n=\sum_k\left\{n\atop k\right\}(x)_k$, where $(x)_k$ is the falling factorial. Consider the $q$-analog recursive definition of the ...
7
votes
1answer
293 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 ...
7
votes
1answer
306 views

How to prove this sequence of inequalities

The number $c_{g}(n)$ is defined by the recurrence \begin{equation} c_{g}(n) = c_{g}(n-1)+ (n-1)(n-2)c_{g-1}(n-2) , \end{equation} with $c_{0}(n)=1$ for any $n\geq 1$ and $c_{g}(n)=0$ if $n \leq 2g$. ...
7
votes
2answers
555 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 ...
7
votes
1answer
199 views

Diagonal of the double sequence $(n+1)v_{h,n+1}-(2h+1)v_{h,n}-nv_{h,n-1}=0$

Update: it is not possible to reply to this question without additional information. My comment below: "I have to agree with you that one "cannot derive (2) from (1) alone". Now it seems to me that ...
7
votes
1answer
407 views

Generating function of words in a binary alphabet counting blocks and appearances

Given the binary alphabet {a,b}, I'm trying to find the generating function that distinguishes, for all words of fixed length $n$, the count of blocks of a's and the number of a's. Let $x^p$ count the ...
7
votes
1answer
345 views

Challenging recurrence relation problem

I am starting out with the following: $$ \frac{d^n}{dx^n}[g(x)^{f(x)}] = \sum_{c=0}^n g(x)^{f(x)-c}\lambda_{n,c}(x) $$ Therefore: $$ \frac{d^{n+1}}{dx^{n+1}}[g(x)^{f(x)}] = ...
7
votes
1answer
254 views

Compute limit of the sequence $x_n$ given by $x_{n+2}=-\frac{1}{2}(x_{n+1}-x_n^2)^2+x_n^4$

Let $(x_n)$ be a real sequence such that $x_0=a\in\mathbb{R},x_1=b\in\mathbb{R},x_{n+2}=-\dfrac{1}{2}\left(x_{n+1}-x_{n}^2\right)^2+x_{n}^4\;\forall n\in\mathbb{N} $ and $|x_n|\leq ...
7
votes
1answer
146 views

What are the solutions for $a(n)$ and $b(n)$ when $a(n+1)=a(n)b(n)$ and $b(n+1)=a(n)+b(n)$?

If you have the following recurrence relations : $a(n+1)= a(n) b(n)$ $b(n+1)= a(n) + b(n) $ How do you find the form of $a(n)$ and $b(n)$ ? I suspect there isn't a closed form , but a infinit sum ...
7
votes
1answer
144 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 ...
7
votes
1answer
50 views

Recurrence $u_{n+1}u_{n-1}-u_n^2=Ar^{n-1}$

I was going through some old puzzles and encountered one where there was a non-linear recurrence of form $$u_{n+1}u_{n-1}-u_n^2=Ar^{n-1}$$ with $u_0$ and $u_1$ given. I know I can use a test form ...
7
votes
1answer
576 views

Any serious work on Lychrel numbers/$196$-Algorithm?

I've been googling around a little lately and have stumbled across the so called Lychrel problem. For a natural number $x$, let $Rx$ denote the number obtained by reversing the base-$10$ digits of $x$ ...
7
votes
0answers
174 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 ...
7
votes
0answers
110 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 ...
7
votes
1answer
108 views

Another recurrence… $T(n)=\sqrt{2n} \cdot T(\sqrt{2n}) + \sqrt{n}$

I'm trying to solve the following recurrence : $$T(n)=\sqrt{2n}\cdot T(\sqrt{2n}) + \sqrt{n}$$ I've tried substituting $n$ for some other variables to transform the above to something easier without ...
7
votes
0answers
91 views

Properties of a continued fraction convolution operation

Usually the partial numerators of a continued fraction are all 1s. Has anyone considered the operation where you convolve 1 continued fraction with another, in other words, make a new continued ...
7
votes
0answers
289 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 !?
6
votes
3answers
4k 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., ...
6
votes
5answers
206 views

How can I find the value of $a^n+b^n$, given the value of $a+b$, $ab$, and $n$?

I have been given the value of $a+b$ , $ab$ and $n$. I've to calculate the value of $a^n+b^n$. How can I do it? I would like to find out a general solution. Because the value of $n$ , $a+b$ and $ab$ ...
6
votes
6answers
1k views

How to find the limit of this recurrence relation?

$a_n$ is a sequence where $a_1=0$ and $a_2=100$, and for $n \geq 2$: $$ a_{n+1}=a_n+\frac{a_n-1}{(n)^2-1} $$ I have a basic understanding of sequences. I wasn't sure how to deal with this recurrence ...
6
votes
2answers
1k views

Recursive square root problem [duplicate]

Give a precise meaning to evaluate the following: $$\large{\sqrt{1+\sqrt{1+\sqrt{1+\sqrt{1+\dotsb}}}}}$$ Since I think it has a recursive structure (does it?), I reduce the equation to $$ ...
6
votes
4answers
148 views

closed form for $d(4)=2$, $d(n+1)=d(n)+n-1$?

I am helping a friend in his last year of high school with his math class. They are studying recurrences and proof by inference. One of the exercises was simply "How many diagonals does a regular ...
6
votes
3answers
492 views

Common term for differential equations and recurrence relations

Recently I have been working with recurrence relations (mostly linear), and systems of coupled recurrence relations. I have noticed a lot of common ground with differential equations. In a way, you ...
6
votes
2answers
65 views

How to evaluate $\lim_{ n\to \infty }\frac{a_n}{2^{n-1}}$, if $a_0=0$ and $a_{n+1}=a_n+\sqrt{a_n^2+1}$?

Let $a_1,a_2,..,a_n$ be sequence of real numbers such that $a_{n+1}=a_{n}+\sqrt{1+a_n^2}$ and $a_0=0$. How to evaluate $\lim_{ n\to \infty }\frac{a_n}{2^{n-1}}$ ?
6
votes
5answers
152 views

$x_{n+1} = \sqrt{3x_n}$ converges for $x_1 = 1,x_1 = 27$ Proof

Prove $x_{n+1} = \sqrt{3x_n}$ converges for $x_1 = 1,x_1 = 27$. (Separate problems for $x_1 = 1$ and $x_1 = 27$.) EDIT: Took out bad algebra.
6
votes
3answers
92 views

Please solve this recurrence relation question for $8a_na_{n+1}-16a_{n+1}+2a_n+5=0$

Suppose $a_1=1$ and $$8a_na_{n+1}-16a_{n+1}+2a_n+5=0,\forall n\geq1,$$Please help to sort out the general form of $a_n$. Here are the first a few values of the series. Not sure if they are useful as ...
6
votes
3answers
246 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
213 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
4answers
280 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, ...
6
votes
2answers
165 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

Concrete Mathematics - Towers of Hanoi Recurrence Relation

I've decided to dive in Concrete Mathematics despite only doing a couple of years of undergraduate maths many years ago. I'm looking to work through all the material whilst plugging gaps in my ...
6
votes
1answer
4k 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
1answer
672 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
2k views

Inductive proof of the closed formula for the Fibonacci sequence [duplicate]

Fibonacci numbers $f(n)$ are defined recursively: $f(n) = f(n-1) +f(n-2)$ for $n > 2$ and $f(1) = 1$, $f(2) = 1$. They also admit a simple closed form: $$\sqrt 5 f( n ) = \left(\dfrac{1+ \sqrt ...
6
votes
2answers
519 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
789 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
302 views

convoluted recurrence: $f(2n)=f(n)+f(n+1)+n, f(2n+1)=f(n)+f(n-1)+1$

For the recurrence relation: $f(0)=1$ $f(1)=1$ $f(2)=2$ $f(2n)=f(n)+f(n+1)+n\ \ \ (\forall n>1)$ $f(2n+1)=f(n)+f(n-1)+1\ \ \ (\forall n\ge 1)$ (the first numbers of the sequence are: 1, 1, 2, ...