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

learn more… | top users | synonyms (2)

6
votes
1answer
892 views

Adapted Towers of Hanoi from Concrete Mathematics - number of arrangements

I have a doubt concerning an exercise from Chapter 1 of "Concrete Mathematics". Actually, my doubt is in one exercise (exercise 3), but, since it depends on the previous exercise (2), I'm including it ...
6
votes
1answer
131 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
105 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
176 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
279 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
4answers
63 views

Proving that the elements of $A^n$ matrix are non-zero

Let $ A = \begin{pmatrix} 1 & 2 \\-1 & 1 \\ \end{pmatrix}$. Prove that for every positive integer $n$ there exist integers $x_{n},y_{n}$ such that $A^n= \begin{pmatrix} x_{n} & -2y_{n} \\ ...
6
votes
1answer
133 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
187 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
330 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
96 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
229 views

recurrence relation $f(n)=5f(n/2)-6f(n/4) + n$

I've been trying to solve this recurrence relation for a week, but I haven't come up with a solution. $f(n)=5f(n/2)-6f(n/4) + n$ Solve this recurrence relation for $f(1)=2$ and $f(2)=1$ At first ...
6
votes
2answers
372 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
169 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
117 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 ...
6
votes
1answer
51 views

The number of series over $\{0,1,2\}$ without repeating numbers

What is the number of series over $\{0,1,2\}$ with length $n$ without repeating the same number one after the other ($22$ is not allowed but $101$ is), that does not begin and end with the number $2$. ...
6
votes
1answer
266 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
1answer
154 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
106 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
185 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 ...
6
votes
0answers
577 views

The Average Running Time Of Euclid Algorithm?

What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$? It seems very hard to deduce from the recurrence $T(m,n) = T(n, m ...
5
votes
5answers
292 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
309 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
524 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
1k 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
124 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
209 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
388 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
2answers
379 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
1answer
201 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
881 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
95 views

A recurrence relation problem: $\frac {a_{n-1}.a_{n+1}} {a_n^2} = 1 + \frac 1 n$

I need to solve this recurrence problem to find $a_n$ $\dfrac {a_{n-1}.a_{n+1}} {a_n^2} = 1 + \dfrac 1 n$ It is what I tried so far: $$\log (\dfrac {a_{n-1}.a_{n+1}} {a_n^2}) = \log(1 + \dfrac 1 ...
5
votes
5answers
976 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
327 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
161 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
137 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
173 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
4answers
506 views

How to solve this recurrence relation?

There's a frog who could climb either 1 stair or 3 stairs in one shot. In how many ways he could reach at 100th stair? I came up with the solution $g(n) = g(n-3) + g(n-1)$, where $g(0)=g(1)=g(2)=1$ ...
5
votes
2answers
280 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
5k views

What is the solution to the following recurrence relation with square root: $T(n)=T (\sqrt{n}) + 1$?

This looks like a question asked earlier, but it isn't. $$T(n)=\begin{cases} T (\sqrt{n}) + 1 \quad & \text{ if } n>1 \\ 1 & \text{ if }n=1\end{cases}$$ My professor gave this to me in ...
5
votes
1answer
334 views

Expanding the generating function of the Fibonacci numbers to find a cute formula

$F_0=1$, $F_1=1$, $F_n=F_{n-1}+F_{n-2}$. The generating function is $-\frac{1}{x^2+x-1}$. I have to expand it to prove that $F_n=\sum_k\binom{k}{n-k}$. Could you help me please?
5
votes
3answers
1k 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 ...
5
votes
3answers
352 views

The number of length-n ternary sequences with even ones and even zeroes

Just starting to appreciate recurrence relations Let $T_n = $ number of length-n ternary sequences with an even number of ones and an even number of zeroes. $T_0 = 1$, because $0$ is an even number, ...
5
votes
2answers
114 views

Proving integrality of a sequence of numbers

How would one go about proving whether or not the terms of a sequence such as the following $$1, 1, 1, 1, 1, 6, 21, 181, 5221, 1090981, 986241401, 51490676208426,\ldots$$ defined by ...
5
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 ...
5
votes
2answers
124 views

Why should we suspect that the recurrence $T(n) = T(n-1) + n(n-1)$ satisfies a polynomial identity?

In the question Algorithms: Recurence Relation, the author asked about the recurrence relation $$T(n) = T(n-1) + n(n-1)$$ and one of the answers proposed assuming $T(n)$ is polynomial, then ...
5
votes
4answers
1k views

Chain rule for discrete/finite calculus

In the context of discrete calculus, or calculus of finite differences, is there a theorem like the chain rule that can express the finite forward difference of a composition $∆(f\circ g)$ in ...
5
votes
1answer
189 views

Solving Recurrence $T_n = T_{n-1}*T_{n-2} + T_{n-3}$

I have a series of numbers called the Foo numbers, where $F_0 = 1, F_1=1, F_2 = 1 $ then the general equation looks like the following: $$ F_n = F_{n-1}(F_{n-2}) + F_{n-3} $$ So far I have got the ...
5
votes
2answers
7k views

How to solve this recurrence $T(n) = 2T(n/2) + n\log n$

How can I solve the recurrence relation $T(n) = 2T(n/2) + n\log n$? It almost matches the Master Theorem except for the $n\log n$ part.