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

learn more… | top users | synonyms (2)

5
votes
2answers
114 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
1k 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
334 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
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
176 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
540 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
1answer
162 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
2answers
297 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
2answers
8k 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.
5
votes
1answer
345 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
390 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
2answers
126 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
197 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
1answer
692 views

On the generating function of the Fibonacci numbers

Let's define the Fibonacci numbers as $F_0=1$, $F_1=1$ and $F_n=F_{n-1}+F_{n-2}$. Using this recurrence I was able to calculate the generating function of the Fibonacci numbers to be ...
5
votes
3answers
144 views

Looking for a function $f$ such that $f(i)=2(f(i-1)+f(\lceil i/2\rceil))$

I'm looking for a solution $f$ to the difference equation $$f(i)=2(f(i-1)+f(\lceil i/2\rceil))$$ with $f(2)=4$. Very grateful for any ideas. PS. I've tried plotting the the initial values into ...
5
votes
4answers
138 views

Recurrence equation: $u_n = 4u_{n−1} + 4u_{n−2}$ ; is $4x+4 = 4$ the characteristic equation?

Given this recurrence equation: $u_1 = 0, u_2 = 1$ $u_n = 4u_{n−1} + 4u_{n−2}$ Is the correct characteristic equation: $4x+4 = 4$ EDIT: Complete solve: The characteristic equation is ...
5
votes
2answers
2k views

Second order homogeneous linear difference equation with variable coefficients

I was wondering if you would point me to a book where the theory of second order homogeneous linear difference equation with variable coefficients is discussed. I am having difficulties in getting ...
5
votes
2answers
178 views

Solving a recurrence for a probability?

I came across the following recurrence relation when exploring properties of a certain type of randomized perfect binary tree: $$ T(0) = \frac{1}{2} $$ $$ T(k + 1) = 1 - T(k)^2 $$ (Specifically, ...
5
votes
1answer
194 views

Finding the general formula $a_n$ for $a_n = \frac{1}{2a_{n-1}} + 2a_{n-2}$

How to calculate the general formula $a_n$ for the following sequence: $$a_n = \frac{1}{2a_{n-1}} + 2a_{n-2}$$ where $a_1=\frac{1}{2}, a_2=\frac{1}{4}$
5
votes
2answers
447 views

Whats better: 1 million dollars in a month or a penny(USD) doubled (and added) every day for 30 days?

THis is a question that I remember when I was in the 5th grade that tested our logical reasoning skills. And it is a simple choice knowing that the pennies doubling every day is an exponential ...
5
votes
1answer
362 views

Summation Of Product Of Fibonacci Numbers

Im trying to find out a general term for the following summation of products of fibonacci numbers:-- $$\sum_{k=4}^{n+1} F_{k}F_{n+5-k}\; , n \geq 3$$ I tried using Binet's equation but I am ...
5
votes
2answers
405 views

Understanding why the roots of homogeneous difference equation must be eigenvalues

There is some obvious relationship between the root solutions to a homogeneous difference equation (as a recurrence relation) and eigenvalues which I'm trying to see. I have read over the wiki article ...
5
votes
1answer
448 views

Towers of Hanoi - are there configurations of $n$ disks that are more than $2^n - 1$ moves apart?

This is an exercise from Chapter 1 of "Concrete Mathematics". It concerns the Towers of Hanoi. Are there any starting and ending configurations of $n$ disks on three pegs that are more than $2^n - ...
5
votes
2answers
606 views

Solving recurrences of the form $T(n)=aT(n/a)+Θ(nlgn)$

On pages 95 and 96 of the third edition of the CLRS book, we find the following, which applies here since $a=b$ is all it takes to block the application of the Master Theorem: "Although $n\lg n$ is ...
5
votes
2answers
173 views

Recurrence relation: composition of a polynomial function

Let $f(x)=a+bx^2$. Define $f_n(x)$ to be the $n$-fold composition of $f$. That is $$f_1(x)=f(x)$$ $$f_2(x)=f \circ f(x)$$ $$f_n(x)=f \circ f_{n-1}(x), n \ge 2$$ Is there a way to find a formula for ...
5
votes
1answer
239 views

When is a recurrence relation linear

In http://www.cs.fsu.edu/~lacher/courses/COT5405/spring07/notes2.html, it says that $T(n) = aT(n/b) + f(n) $ is nonlinear recurrence. But I think it is linear because $T(n)$ is linear in $T(n/b)$. ...
5
votes
3answers
757 views

how to solve $T (n) = T \left(\frac{n}{2} +\sqrt{n}\right) +\sqrt{6046}$

How can I solve the recurrence $$T (n) = T \left(\frac{n}{2} +\sqrt{n}\right) +\sqrt{6046}\ ?$$ Please don't just write the name of the method, as I just started learning this stuff and things are a ...
5
votes
2answers
228 views

Method of solving no-homogeneous recurrence equation

I need to obtain a closed form of $M(t)$, satisfying the following recurrence equation: $$M(t+1)=a+bM(t)+\frac{c}{t+1}\sum_{t'=0}^tM(t')+df(t)$$ Where $f(t)$ is a known function and $a$, $b$, $c$ ...
5
votes
1answer
147 views

Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$ \begin{array}{cccccccccc} 1 & = & ...
5
votes
3answers
697 views

Number of Regions in the Plane defined by $n$ Zig-Zag Lines

Fellows of Math.SE, I have been scratching my head at a solution to an exercise in Donald Knuth's Concrete Math. Here is the problem: Here is the solution (I hid it in case someone wants to solve ...
5
votes
3answers
67 views

Divergence of $a_{n+1}=\sqrt{2a_n+3}$?

I am wondering what I am missing from my proof. I would like to show that the limit of the sequence $$a_{n+1}=\sqrt{2a_n+3},\,\, a_1=4,$$ goes to $\infty$, as $n \rightarrow \infty$. Is there ...
5
votes
2answers
323 views

If a recursive sequence converges, must its inverse be divergent?

Suppose I have a recursive sequence $\displaystyle a_{n+1} = \frac{a_{n}}{2}$. Clearly, the sequence converges towards zero. Now, suppose I define an "inverse" sequence $\displaystyle b_{n+1} = ...
5
votes
2answers
179 views

Let $x_{n+1} = x_n + 1/(x_1 + x_2 +\ldots + x_n)$ with $x_1 = 1$. Show that $x_n\sim\sqrt{2\log(n)}$.

As the title states we have a sequence defined by $$x_{n+1} = x_n + \dfrac{1}{x_1 + x_2 + \cdots + x_n}$$ with $x_1 = 1$. The first few terms are: $1, 2, \frac{7}{3}, \frac{121}{48} \cdots$ Any ...
5
votes
3answers
234 views

Solve the recursion, $a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}+8$

Bring the following recursion relation to an explicit expression: $$a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}+8$$ $a_{0} = 0$, $a_1 = 1$, $a_2 = 2$ All the examples I have seen were with maximum 2 steps back ...
5
votes
2answers
64 views

Let $A$ be a matrix sized $p\times p$, where $2\le p$. Using recurrence relations, describe $A^k$.

Let $A$ be a matrix sized $p\times p$, Where $2\le p$. The matrix values in the main diagonal are $0$ and the rest are $1$'s. Example for $A$ where $p=5$: $$\begin{bmatrix} 0 & 1 & 1 & 1 ...
5
votes
1answer
290 views

Recurrence for perfect matchings revisited.

I like to study combinatorics a bit as a hobby, and recently a question I found interesting was posed asking to derive a recurrence for the generating function $G_n(x)$, the ordinary generating ...
5
votes
1answer
309 views

two-dimensional recurrence

Can someone using only these conditions $$a_{m,k}=a_{m-1,k}+a_{m-1,k-1},m>k$$ $$a_{m,k}=1,m=k$$ $$a_{m,k}=0,m<k$$ prove that $$a_{m,k}=\frac{m!}{k!(m-k)!}$$ here is way to construct Pascal ...
5
votes
1answer
455 views

Show that the Catalan numbers are given by this recurrence relation

Hey guys! I'm doing an assignment, and I'm just not sure (at all) how to start this problem. Can somebody nudge/shove me in the right directions? Show that the Catalan numbers are given by the ...
5
votes
1answer
160 views

What is the expected number of questions answered to complete a sequence in which wrong answers send you to the start?

Given a sequence of n questions that each contain x answer choices, what is the expected number of questions answered before answering all questions correctly if answering a question incorrectly sends ...
5
votes
2answers
103 views

Proving a solution to a double recurrence is exhaustive

The equation $$ b^2 = \frac{a(a+1)}{2} + 1 $$ where $a$ and $b$ are integers, has the following smallish-integer solutions: ...
5
votes
1answer
142 views

Period doubling bifurcation in a quadratic map

I am attempting the find $\mu$ for which the map $$x_{n+1} = \mu + x_n^2$$ undergoes a period doubling bifurcation. I understand that finding the fixed points of the map is the first step towards ...
5
votes
1answer
88 views

Expressing a recursively defined function in terms of factorials or gamma function

Given the recursion $$f(n) = nf(n-1) + (n-1)f(n-2) $$ $$f(0) = 1, f(1) = 1$$ How exactly does one express the target function? I know that $$f(n) = nf(n-1)$$ gives rise to $$f(n) = ...
5
votes
3answers
390 views

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

How can I solve the recurrence relation $$T(n)=2T\left(\frac n2\right)+\frac{n}{\log n}$$? I am stuck up after few steps.. I arrive till $$T(n) = 2^k T(1) + \sum_{i=0}^{\log(n-1)} ...
5
votes
1answer
508 views

Deriving a recurrence relation

The number of sequences of length $n$ consisting of positive integers such that the opening and ending elements are $1$ or $2$ and the absolute difference between any $2$ consecutive elements is $0$ ...
5
votes
1answer
123 views

Geometric interpretation of the fundamental theorem for coalgebras?

Given an element $m$ in a coalgebra $C$, there always exists a finite-dimensional subcoalgebra $D \subset C$ containing $m$; this is the fundamental theorem for coalgebras. This obviously isn't the ...
5
votes
1answer
167 views

general technique to convert recurrence relation to integral

I know the following recurrence relation $$a_n=\frac{a+na_{n-1}}{a-n}$$ with $a_0=1$ can be represented alternatively as an integral $$a_n=a\int_0^1{x^{a-n-1}(2-x)^ndx}$$ Verifying this is easy, ...