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

learn more… | top users | synonyms

5
votes
1answer
189 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
794 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
353 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
815 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
318 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
133 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
163 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
244 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
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
233 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
179 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
585 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
4answers
131 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
377 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
308 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
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
229 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
687 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
94 views

partitions and their generating functions and Partitions of n

A partition of an integer, n, is one way of writing n as the sum of positive integers where the order of the addends (terms being added) does not matter. p(n, k) = number of partitions of n with k ...
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
1answer
366 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
3answers
64 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
168 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
175 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
523 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
222 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
430 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
36 views

Find a Recurrence Relation

I want to find a recurrence relation for number of decimal numbers with length n, (we called $a_0$ ) that not includes 0 and any combination of 11,12, 21. i see the result is: ...
5
votes
2answers
63 views

Recurrence Relation from Old Exam

I see this challenging recurrence relation that has a solution of $T^2(n)=\theta (n^2)$. anyone could solve it for me? how get it? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 ...
5
votes
1answer
265 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
43 views

A nice recurrence sequence

I want to find general solution for recurrence: $a_n=7a_{n-1}-10a_{n-2}+4n$ with suppose $c_1, c_2, c_3$ is constant. I need some tutorial or solution on this challenging recurrence.
5
votes
1answer
78 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
97 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
179 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
344 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
91 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
159 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, ...
5
votes
1answer
239 views

A nicer recurrence for the Eulerian polynomials.

I was perusing the subject of Eulerian polynomials. I'm assuming the definition that the Eulerian polynomial is defined by $C_n(t)=\sum_{\pi\in S_n}t^{1+d(\pi)}$, where $d(\pi)$ is the number of ...
5
votes
1answer
44 views

Recursive identity for elliptic lattice constants $\sum_{\lambda\in\Lambda\setminus0} \lambda^{-2k}$

I am stuck on Exercise 3 in these notes. To keep this question self-contained: we have $\displaystyle\Lambda=\langle\omega_1,\omega_2\rangle=\omega_1\Bbb Z+\omega_2\Bbb Z\subset\Bbb C,$ ...
5
votes
4answers
98 views

Homework | Find the general solution to the recurrence relation

A question I have been stuck on for quite a while is the following Find the general solution to the recurrence relation $$a_n = ba_{n-1} - b^2a_{n-2}$$ Where $b \gt 0$ is a constant. I don't ...
5
votes
1answer
370 views

Purely combinatorial proof and simplification of identity involving factorials and summations

While trying to decompose factorials into summations, I came up with the following identity $$(n+2)! = 2^{n+1} + \sum\limits_{k=0}^{n-1}\sum\limits_{i=0}^{n-1-k}\sum\limits_{S \subseteq ...
5
votes
3answers
307 views

Find inverse for the closed-form expression of linear recurrence relation

I am trying to find an inverse of the following formula: $$ a_n=\frac{2+\sqrt{6}}{4}(1+\sqrt{6})^n+\frac{2-\sqrt{6}}{4}(1-\sqrt{6})^n $$ This formula is a closed-form expression of a linear ...
5
votes
1answer
74 views

Recurrence-differential equation

In his book on differential equations, Arnold writes that $x'(t)=x(x(t))$ is not a differential equation. My question is: how can one solve it?