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

learn more… | top users | synonyms

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
65 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
137 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
300 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
143 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
605 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
279 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
163 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
147 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
305 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
271 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
1answer
92 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
407 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
112 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
88 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
81 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
195 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
626 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
300 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
165 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
66 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
154 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
349 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
1answer
250 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
87 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
119 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
450 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 ...
4
votes
3answers
127 views

How do you solve this recurrence?

I have been trying to practice recurrence relations that can be solved by the master theorem and came across this. Now the $4^{\textrm{th}}$ problem in that file is : $$T(n) = 2^n ...
4
votes
2answers
215 views

Help on a rational recursive relation: $T[n+1]=\frac{E[n+1](D+T[n])}{E[n+1]+D+T[n]}$

I am trying to solve this rational recursive relation: $$T[n+1]=\frac{E[n+1](D+T[n])}{E[n+1]+D+T[n]}$$ where $T[1]=\frac{E[1]*D}{E[1]+D}$ for constant $D>0$ and $E[n]>0$. When $E[n]$ is ...
4
votes
1answer
111 views

finding hypergeometric solutions for a recurrence relation

I would like to find all the possible hypergeometric solutions for the recurrence relation defined as $$ (n+2)a_{n+2} - 2(4n+5)a_{n+1} + 8(2n+1)a_n = 0.$$ Is there any way to approach this problem in ...
4
votes
2answers
140 views

recurrence relation $f(n)=5f(n/2)-6f(n/4) + n$

I've been trying to solve this recurrence relation for a week, but I haven't come up with a solution. $f(n)=5f(n/2)-6f(n/4) + n$ Solve this recurrence relation for $f(1)=2$ and $f(2)=1$ At first ...
4
votes
1answer
74 views

Generating a recurrence relation

Suppose you have a large collections of red 1x2 tiles, blue 1x2 tiles and green 1x2 tiles. For $n\ge 0$, let $t_n$ be the number of ways to use these to exactly cover the squares of a 2xn checkerboard ...
4
votes
2answers
50 views

Generating a recurrence relation question

A switching game has $n$ switches, all initially in the OFF position. In order to be able to flip the $ith$ switch, the $(i-1)st$ switch must be ON, and all earlier switches OFF. The first switch can ...
4
votes
1answer
158 views

Solve the recurrence: $f(n, k) = f(n-1, k-1) + f(n-1, k) + 2^n$

This is somewhat like Pascal's triangle but with an additional $2^n$: $$\left\{\begin{align*} &f(n,0)=f(n,n)=2^n-1\\ &f(n,k)=f(n-1,k-1)+f(n-1,k)+2^n \end{align*}\right.$$ Is there a direct ...
4
votes
1answer
76 views

Solving recurrence relation of the form $T(n)=T\left(\frac{nb}{a}\right)+T\left(\frac{(n-b)c}{a}\right)+n$

How do we solve a recurrence of the form: $T(n)=T\biggl(\dfrac{nb}{a}\biggr)+T\biggl(\dfrac{(n-b)c}{a}\biggr)+n$ ? I tried substituting $q=\dfrac{a}{b},\ r=\dfrac{a}{c}, \ s=\dfrac{bc}{a}$ to ...
4
votes
1answer
166 views

Recurrence relation for a function with an integral of the function?

Pardon my lack of tex skills, but what is the recommended procedure in the following scenario: $$g(f) = 1+\int_0^{1-f} g\left(\dfrac{f}{1-x}\right)\,dx$$ I am not sure how to proceed in such a ...
4
votes
2answers
1k views

Recurrence $T(n)=T(n/2)+2^n$ and $T(n)=T(n/2+\sqrt n)+\sqrt{6044}$ , without (!) the master method

Given the Recurrences $$T(n)=T(n/2)+2^n$$ and $$T(n)=T(n/2+\sqrt n)+\sqrt{6044}$$ Remark : $T(n)=1$ for $n\le 3$ I'm trying to find their upper bound & lower bound , which is probably $O(2^n)$ ...
4
votes
1answer
222 views

What types of functions do recurrence relations methods apply to?

I have been working with a function that I defined recursively as $$a(n) = (1-a(n-1)^k)^k$$ where $a(0) = x$ and $k$ is an integer $>1$. So really, $a(n)$ returns a function on $x$ and $k$. I have ...
4
votes
0answers
32 views

How to solve a non-homogeneous second-order linear difference equation with both a forward and a backward difference?

Quite a long title for this: I'm looking for the general solution of the following difference equation: $$ax_{t+1} -bx_t + x_{t-1} = c + u_t$$ where $a,b,c$ are real constants and $u_t$ is a bounded ...
4
votes
0answers
69 views

Nonlinear inhomogeneous recurrence $f(x)^2=f(x+1)+S(x)$ to find nested radical

I want to solve the recurrence relation $$f(x)^2=f(x+1)+S(x)$$ where $S(x)$ is a given polynomial. The background is to find nested radicals expressions of the form ...
4
votes
1answer
65 views

How to *really* solve a non-homogeneous recurrence

First let me state that I am not asking about the usual procedure for finding a trial solution to a non-homogeneous recurrence. I have been doing this for many years and can solve all the basic ...
4
votes
0answers
50 views

Transform recurrence relation

Is it possible to transform following recurrence relation $a_n=4a_{n-2}-a_{n-4}$, $a_0=1$, $a_1=0$, $a_2=3$, $a_3=0$ so that it will have nonnegative coefficients? Number of terms, of course, can be ...