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

learn more… | top users | synonyms (2)

7
votes
0answers
66 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
0answers
91 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
102 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
85 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
246 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
5answers
201 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
772 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
142 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
414 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
5answers
149 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
90 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
236 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
202 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
224 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
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
2answers
139 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
558 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
469 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
592 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
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
147 views

permutation and f(n) challenge

Suppose $f(n)$ be the number of permutation from set ${1,2,..,n}$ such that for each $ 1 \leq i \leq n$ we have: $ | \pi(i)-i| \leq 1 $. meaning of $ \pi(i)$ is an elements whose in place $i$ of ...
6
votes
2answers
119 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
124 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
1answer
334 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
2answers
87 views

Count with only certain digits allowed - And feel a fractal

I have a friend ~200 years old mathematician who has forgotten some digits and now he counts things in very strange manner: when he is going to count the $n$-th thing and $n$ contains a digit he ...
6
votes
2answers
152 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
129 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
99 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
2answers
166 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
2answers
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 ...
6
votes
1answer
271 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
1answer
131 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
186 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
298 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
271 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
1answer
82 views

A proof by strong induction that $a_n\le3^n$ where $a_n=a_{n-1}+a_{n-2}+a_{n-3}$

I am not sure whether this is right. Can anyone verify, whether this proof is valid? Thanks! Define a sequence $\{a_n\}_{n\ge0}$ as follows: ...
6
votes
2answers
366 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
152 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
2k views

Solving recurrence $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n)$

I'm learning algorithms by myself and am using the excellent Introduction to algorithms to do that. It has been quite a long time since I last studied math, so maybe the solution to my problem is ...
6
votes
1answer
229 views

Recursion relation of fourth order Runge-Kutta method applied on system

I'm trying to apply the Gauss-Legendre method of fourth order (as Runge-Kutta method) on the following system of equations $$\left\{ \begin{matrix} \dot{a} =& -b \\ ...
6
votes
2answers
377 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
152 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
94 views

Minimizing beginning terms of a Fibonacci-like sequence

For $ a, b \in \mathbb{Z}^+ $ such that $ a = b $ or $ 2a < b $, let $ f_{a, b} : \mathbb{Z}^+ \to \mathbb{Z}^+ $ be a sequence that satisfies the following three criteria: $$ f(1) = a, \\ f(2) = ...
6
votes
0answers
122 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 ...
6
votes
0answers
98 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
166 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
3answers
3k 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., ...
5
votes
5answers
274 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
306 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)$?