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

learn more… | top users | synonyms (2)

5
votes
4answers
509 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
710 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
108 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
202 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
371 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
335 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
191 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
810 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
5answers
361 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
835 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
321 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
157 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
135 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
164 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
249 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
1answer
304 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
280 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
119 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
1answer
184 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
596 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
140 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
133 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
381 views

Series of sequence converges?

Given the recursively defined sequence $$ a_2 = 2(C+1)a_0 $$ and $$ a_{n+2}=\frac{\left(n(n+6)+4(C+1)\right)a_n - 8(n-2)a_{n-2}}{(n+1)(n+2)}. $$ that I got from the Frobenius method applied to an ODE, ...
5
votes
2answers
167 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
188 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
328 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
4answers
4k views

What is the solution to the following recurrence relation with square root?

This looks like a question asked earlier, but it isn't T(n) = T (sqrt(n)) + 1 ... if n>1 =1... if n=1 My professor gave this to me in class yesterday. This is where I'm stuck.. T(n) ...
5
votes
2answers
160 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
232 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
2answers
1k 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
3answers
689 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
3answers
766 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
369 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
1answer
180 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$ $f(2n+1)=f(n)+f(n-1)+1$ (the first numbers of the sequence are: 1, 1, 2, 3, 7, 4, 13, 6, 15, 11, 22, 12, 25, 18, 28) ...
5
votes
3answers
65 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
172 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
181 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
63 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
2answers
528 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
1answer
229 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
2answers
433 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
268 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
2answers
52 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
80 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
1answer
98 views

Recurrence for random walk

I have the following recurrence which I get when trying to solve a random walk problem given a positive integer $x$. $p_i = \dfrac{p_{i-1}}{2} + \dfrac{p_{i+2}}{2}$ if $0< i < x$ $p_i = 1$ if ...
5
votes
3answers
190 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
355 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
2answers
265 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 ...