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

learn more… | top users | synonyms

4
votes
1answer
353 views

$a_n=20a_{n-1}+12a_{n-2}$ recurrence relation question

Respected Sir, Please solve the below problem. Please... Consider the infinite $\displaystyle\mathbb{S}=\sum_{n=0}^{\infty}\frac{a_n}{10^{2n}}$, where the sequence $\{a_n\}$ is defined by ...
4
votes
3answers
1k views

Recurrence trouble: $T(n)=2T(n/2)+T(n/3)+\theta(n^2)$

I have to solve the following recurrence :$\displaystyle T(n)=2T(n/2)+T(n/3)+\theta(n^2)$ I have done the whole tree analyses and now I have to prove that $\displaystyle T(n) \leq ...
4
votes
5answers
90 views

How to solve the recurrence relation $T(n) = T(\lceil n/2\rceil) + T(\lfloor n/2\rfloor) + 2$

I'm trying to solve a recurrence relation for the exact function (I need the exact number of comparisons for some algorithm). This is what i need to solve: $$\begin{aligned} T(1) &= 0 \\ T(2) ...
4
votes
3answers
159 views

How does $\tbinom{4n}{2n}$ relate to $\tbinom{2n}{n}$?

I got this question in my mind when I was working on a solution to factorial recurrence and came up with this recurrence relation: $$(2n)!=\binom{2n}{n}(n!)^2$$ which made me wonder: is there also a ...
4
votes
3answers
206 views

Combinatorial Proof for a Recursive Sequence

For $n>3$ let $g_n = g_{n-1} + g_{n-3}$ where the recursion takes the value 1 for n = 0,1,2. Prove that $g_{2n} = (g_n)^2 + 2g_{n-2}g_{n-1}$ combinatorially, $n > 1$. For the time being I am ...
4
votes
3answers
124 views

Need help about solving a recurrence relation

I have a recurrence relation which is like the following: $$ T(n) = 2T(n/2) + \log_2 n. $$ I am using recursion tree method to solve this. And at the end, i came up with the following equation: $$ ...
4
votes
3answers
189 views

Maximum based recursive function definition

Does a function other than 0 that satisfies the following definition exist? $$ f(x) = \max_{0<\xi<x}\left\{ \xi\;f(x-\xi) \right\} $$ If so can it be expressed using elementary functions?
4
votes
4answers
161 views

What sort of math is this, and how would I solve it?

I'm taking a computer science class after several years away from school and so far I'm doing all right. However, we're covering some math and I'm drawing a blank on what to even call this concept, ...
4
votes
1answer
544 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 ...
4
votes
1answer
95 views

Going from closed form to recurrence relation

If I had a closed form for a sequence that I suspect to represents a recurrence relation how would I determine the recurrence relation? In particular, I have the sequence $$a_n = ...
4
votes
1answer
57 views

Non-linear Recurrence relation

I am concerned to solve the recurrence relation $T(n)=nT^2\left(\frac{n}{2}\right)$ with initial condition T(1)=6. I have tried to do some transformation like $N=2^k$ and some other things like that ...
4
votes
3answers
66 views

Solving a set of recurrence relation:

Solving a set of recurrence relation: $a_n=3b_{n-1} , b_n=a_{n-1}-2b_{n-1}$ In addition, It's known that: $a_1=2, b_1=1$. So i started by isolating $b_n \to b_n=3b_{n-2}-2b_{n-1}$ So i get the ...
4
votes
2answers
138 views

Combinatorial solution to a recurrence problem

I found today this problem in some old blog post: Suppose that $a_n$ is a sequence of positive integers such that $$ \sum_{d |n} a_d =2^n$$ for every positive integer $n$. Prove that $ n | a_n$. It ...
4
votes
2answers
302 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 ...
4
votes
2answers
144 views

A mouse leaping along the square tile

A $n \times n$ square is made of square tiles of dimensions $1\times1$. A mouse can leap along the diagonal or along the side of square tiles. In how many ways can the mouse reach the right lower ...
4
votes
2answers
619 views

How to approach 2-Dimensional Recurrence Relations

How to solve the following 2-dimensional recurrence relation? Let $n, n'$ be natural numbers $> 0.$ Let $r$ be a positive integer $\ge 0.$ $$ P(n+n',r) = \sum_{i=0}^{r} P(n, ...
4
votes
2answers
285 views

Recurrence for $q$-analog for the Stirling numbers?

I read in some papers that the Stirling numbers (of the second kind) have a natural $q$-analog $S_q(n,k)$, which satisfy the recurrence $$ S_q(n,k)=(k)_qS_q(n-1,k)+q^{k-1}S_q(n-1,k-1) $$ with the ...
4
votes
2answers
166 views

Solving a recurrence using substitutions

I have to solve this recurrence using substitutions: $(n+1)(n-2)a_n=n(n^2-n-1)a_{n-1}-(n-1)^3a_{n-2}$ with $a_2=a_3=1$. The only useful substitution that I see is $b_n=(n+1)a_n$, but I don't know ...
4
votes
2answers
148 views

Limit of certain recurrence relation

So given this recurrence relation (not how it was presented, but equivalent and much nicer) $$ x_{n+1} = \dfrac{x_n + nx_{n-1}}{n+1}; \ x_0 = 0,\ x_1 = 1 $$ I just can't find what the limit as $n$ ...
4
votes
1answer
323 views

The characteristic polynomial of a recurrence relation.

If I have a linear homogeneous recurrence relation $$y_n=c_1y_{n-1}+\ldots+c_ky_{n-k},$$ I can get its characteristic equation, which is $$r^k=c_1r^{k-1}+\ldots+c_k.$$ In particular for ...
4
votes
1answer
295 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 ...
4
votes
4answers
156 views

Expansion of $x^4\over1+x^2$ into a power series

I calculated the generating function $A(x)$ of the recurrence $a_n = a_{n-2} - 2a_{n-3}$, $(n \ge 0, a_0 = a_1 = 0, a_2 = 2)$ and I have no clue on how to expand it into a power series in order to ...
4
votes
4answers
1k views

Closed form solution of Fibonacci-like sequence

Could someone please tell me the closed form solution of the equation below. $$F(n) = 2F(n-1) + 2F(n-2)$$ $$F(1) = 1$$ $$F(2) = 3$$ Is there any way it can be easily deduced if the closed form ...
4
votes
2answers
166 views

Count the number of divisions of a set recursively

I'm trying to understand the reasoning behind the answer to the following question from an old exam. Given a set $S_n = \{ 1, 2, 3,\dots n\}$ find how many divisions, $K_n$, there are of the set ...
4
votes
1answer
99 views

Does this sequence consist of squares of integers?

Question: let sequence $\{x_{n}\}$ such $$x_{0}=0,x_{1}=1,x_{2}=0,x_{3}=1$$ and such $$x_{n+3}=\dfrac{(n^2+n+1)(n+1)}{n}x_{n+2}+(n^2+n+1)x_{n+1}-\dfrac{n+1}{n}x_{n}$$ show that:$ ...
4
votes
1answer
94 views

Is there a generating function for $\sqrt{n}$?

I tried to come up with a closed form for the ordinary generating function for the sequence $\{\sqrt{n}\}_0^{\infty}$ but I could not. Is there a way to derive it using the recurrence relation ...
4
votes
1answer
458 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 ...
4
votes
1answer
114 views

Recurrence $a_n = \sum_{k=1}^{n-1}a^2_{k}, a_1=1$

This seems like a really straightforward recurrence. I wrote out the first few terms: $1,1,2,6,42,1806$... It seems to grow faster than $n!$ but slower than $n^n$. Any suggestions about the closed ...
4
votes
4answers
115 views

If $T(n) = \sum_i T(\lfloor r_i n \rfloor) $ for $n \ge 1$, then $T(n)/n \to 0$

Let $(r_i)_{i=1}^m$ be a sequence of positive reals such that $\sum_i r_i < 1$ and let $t$ be a positive real. Consider the sequence $T(n)$ defined by $T(0) = t$, $T(n) = \sum_i T(\lfloor r_i n ...
4
votes
3answers
89 views

Can anyone help me finding recurrence relation in combinatoric?

Guys, I am having trouble finding recurrent relation. A codeword is made up of the digits $0,1,2,3$ (order is important!). A codeword is defined as legitimate if and only if it has an even number of ...
4
votes
1answer
83 views

Find the common limit of $\frac{2}{1/a_n+1/b_n}$ and $\sqrt{a_n b_n}$

Let $a_0=1$ and $b_0=2$, then \begin{align} a_{n+1} &= \frac{2}{\frac{1}{a_n}+\frac{1}{b_n}}, \\ b_{n+1} &= \sqrt{a_n b_n}. \end{align} The sequences $(a_n)$ and $(b_n)$ converge to the same ...
4
votes
2answers
196 views

Enumerate certain special configurations - combinatorics.

Consider the vertices of a regular n-gon, numbered 1 through n. (Only the vertices, not the sides). A "configuration" means some of these vertices are joined by edges. A "good" configuration is one ...
4
votes
1answer
642 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 ...
4
votes
2answers
305 views

Determining a recurrence relation (Homework)

Let ${d_n}$ be the number of DNA strings of length n that contain a pair of consecutive nucleotides of the same type. There are four symbols used in strings of DNA: A, C, G, T. The nucleotides are ...
4
votes
1answer
6k views

Recurrence relation for number of ternary strings that contain two consecutive zeros

The question is: Find a recurrence relation for number of ternary strings of length n that contain two consecutive zeros. I know for ternary strings with length one, there are 0. For a length of 2, ...
4
votes
2answers
2k views

Linear Algebra: Finding a steady state matrix

Here is the problem: And here is what I tried to do: I tried doing it in my calculator and got that the answer is 40 and 160 as you keep multiplying PX. Can anyone point out what I'm doing wrong ...
4
votes
1answer
37 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 ...
4
votes
1answer
43 views

Is it possible to calculate the roots of the difference between successive terms of this polynomial series $\rm{P}_n (x)=x\rm{P}_{n-1}-r\rm{P}_{n-2}$

Consider the polynomial series defined by the following recursion formula: $$ \begin{align} &\mathrm{P}_0 = 1 \\ &\mathrm{P}_1 = x-r \\ &\mathrm{P}_n = x\mathrm{P}_{n-1} - ...
4
votes
1answer
67 views

Find recursive forumula for integrals

I have to find recursve formulas for solving the following two integrals. The assignment tells one to find an Expression that leads from the calculation of $\dfrac{I_{2n}}{I_{2n+1}}$ to the ...
4
votes
3answers
162 views

How to solve a 2nd order non-homogeneous linear recurrence?

I have a problem in solving this equation : $x_{n+2} + 3\ x_{n+1} + 2\ x_{n} = 5 \times 3^n $ given that $x_{0} = 0$ and $x_{1} = 1$. I solved the homogeneous associated equation and got $v_{n} = ...
4
votes
2answers
1k views

Recurrence relation for number of bit strings of length n that contain two consecutive 1s

I'm pulling my hair out over a review question for my final tomorrow. Find a recurrence relation (and its initial conditions) for the number of bit strings of length n that contain two consecutive ...
4
votes
2answers
425 views

Solving the recurrence relation $T(n)=2T(n/4)+\sqrt{n}$

I've solved $T(n)=2T(n/4)+\sqrt{n}$ to equal $2^{\log_{4}n}(\log_{4}n+1)$, but I'm not sure how to solve it directly. I have: $2(2T(\frac{n}{16})+\sqrt{\frac{n}{4}})+\sqrt{n} = ...
4
votes
1answer
362 views

Non-linear Recursion

I'm trying to prove (or disprove and improve if possible) that the sequence $a_{n+1}=\frac{a_n^2+1}{2}$, where $a_0$ is an odd number greater than 1 contains an infinite number of primes. However, I ...
4
votes
2answers
458 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 ...
4
votes
1answer
253 views

Solving (and proving) a combinatorial functional recursive equation

I have a sequence of functions $f_k(n)$ defined as follows: $f_1(n)=n^{n-2}$ $f_k(n)=\sum_{i=1}^{n-1}f_{k-1}(i)\cdot(n-i)^{n-i-2}\cdot{n-k \choose n-i-1}$ My goal is to find and prove a closed-form ...
4
votes
3answers
197 views

If $f(1) = 2$ and $f(n) = n \cdot f(n-1)$ then $f(n) \gt 2^n$ for all $n \gt 2$

I'm having a little difficulty in proving what are probably simple induction proofs. Here is the question. Define function $f(n)$ as follows. $f(1) = 2$ and $f(n) = n\cdot f(n-1)$ when $n > 1$. ...
4
votes
1answer
90 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 ...
4
votes
1answer
122 views

Recursive sequence with binomial coefficients

I have a sequence $\epsilon_i$ defined recursively for $i\ge 1$ as follows \begin{eqnarray*} \epsilon_1 &=& \frac{1}{p}\\ \epsilon_n &=& \frac{1}{1-(1-p)^n}\left( 1 + \sum_{j=1}^{n-1} ...
4
votes
1answer
77 views

$ n $ lines intersections

As we all know, $ n $ lines which are not coincident may have some intersection points in an Euclid plane. And we define the set of the number of intersection points $ n $ lines can form is $ ...
4
votes
1answer
454 views

Finding recurrence relations in combinatorics

I'm working my way through basic combinatorics questions with recurrence relation, and can't quite get my head about the right way of solving them. For example, I have two following examples in my ...