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

learn more… | top users | synonyms

4
votes
3answers
2k views

Solving $T(n)= 2T(n/2)+n \lg (n)$

I am trying to solve a recursive function: $$ T(n)= 2 T(n/2)+n \lg(n), \quad n>2,\quad T(2)=2,\quad n = 2^{k}$$ Master theorem didn't work. The result is pointless (if I did it right). Any ...
4
votes
1answer
354 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
91 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
126 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
190 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
545 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
96 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
623 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
167 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
149 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
327 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
469 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
197 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
673 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
306 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
45 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
163 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
1answer
2k views

Upper bound for $T(n) = T(n - 1) + T(n/2) + n$ with recursion-tree

I'm reading through Introduction to Algorithms, 3rd ed. and I got stuck on the following recurrence (exercise 4.4-5): $$T(n) = T(n - 1) + T(n/2) + n$$ The exercise asks you to find the upper bound ...
4
votes
2answers
427 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
364 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
459 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} ...