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

learn more… | top users | synonyms (2)

2
votes
4answers
147 views

Solving recurrence relation, $a_n=6a_{n-1} - 5a_{n-2} + 1$

I'm trying to solve this recurrence relation: $$ a_n = \begin{cases} 0 & \mbox{for } n = 0 \\ 5 & \mbox{for } n = 1 \\ 6a_{n-1} - 5a_{n-2} + 1 & \mbox{for } n > 1 ...
9
votes
1answer
267 views

What is a good asymptotic for $f_n = f_{n-1}+\ln(f_{n-1})$?

Let $f_0=2$ and $f_n=f_{n-1}+\ln(f_{n-1})$. What is a good asymptotic to the sequence $f_n$? With good I mean much better than $f_n \sim \dfrac{3n \ln(2)\ln(n)}{2}$.
1
vote
5answers
493 views

How can this $T(n) = T(n-1)+T(n-2)+3n+1$ non homogenous recurrence relation be solved

How are can the above recurrence relation be solved? I've reached here: $(x^{2}-x-1)(x-3)^2(x-1)$ And then here: $$a_n = l_1 \cdot (x_1)^n+l_2 \cdot (x_2)^n+l_3 \cdot (x_3)^n+l_4\cdot n \cdot ...
2
votes
1answer
171 views

Register Machine on Fibonacci Numbers

This problem is easy to understand but I am struggling to come up with any solutions. According to Wikipedia a register machine is a generic class of abstract machines used in a manner similar to a ...
3
votes
4answers
115 views

Closed form of a recurrence relation using generating functions

It's been awhile since I have done this. The sequence is $\displaystyle a_n = a_{n-1} + 5~a_{n-2}$ with $a_{0}=0$ and $a_{1}=1$. I found the generating function to be $\displaystyle G(x) = ...
3
votes
2answers
751 views

Non-homogeneous linear recurrence relation

I have this recurrence relation to solve: $$a_{n+1}=3a_n+2^{n-1}-1.$$ The homogeneous part's solution is obviously $a_n=k3^n.$ Now I don't know how to solve the original equation, but I do know what ...
12
votes
1answer
225 views

A series: $1-\frac{1}{2}-\frac{1}{3}-\frac{1}{4}+\frac{1}{5}-\frac{1}{6}+\frac{1}{7}+\cdots$

Denote $$b_1=1,b_{n}=b_{n-1}-\dfrac{S(b_{n-1})}{n},(n>1 )\tag1$$ where $S(x)=1$ if $x>0,S(x)=-1$ if $x<0$, and $S(0)=0.$ So ...
3
votes
3answers
54 views

A problem on recurrence relation

Consider the sequence $$a_n = a_{n-1} a_{n-2} +n$$ for $n \geq 2$, with $a_0 = 1$ and $a_1 = 1$. Is $a_{2011}$ odd? By writing all the terms of the sequence I see that $a_n$ is odd when $n$ is odd ...
1
vote
3answers
52 views

How can I solve this recurrence?

I have a weird recurrence relation and don't know how to solve it: $$a_n = pa_{n-1} + qa_{n+1} + cb_n$$ $$b_n = p'b_{n+1} + q'a_n$$ $$a_0 = 1$$ $p,q,c,p',q' \in [0,1]$ and $p+q+c=1,p'+q'=1$. Thanks ...
2
votes
3answers
3k views

Finding the explicit formula for a recursive sequence, using power series

The Task is to find the explicit expression for the given recursive sequence with the help of power series. Given: $a_{0}=0,\ a_{1}=1 \quad$ and $\quad a_{n}=5\cdot a_{n-1} -6\cdot a_{n-2}\quad $ ...
3
votes
6answers
98 views

How to prove a limit with a recurrence?

$s_1 = 1$ and $s_{n+1} = \dfrac{s_n + 1}{3}$ for $n \in \Bbb N$. How do you find $\displaystyle \lim_{x\to \infty} s_n$? Then how do you prove that the value is the limit using the definition of the ...
2
votes
1answer
172 views

Heighway dragon and twindragon relation

The Heighway dragon F is defined as the limit set for the iterated function system $\begin{cases}f_1(z)=\frac{1+i}2 z\\f_2(z)=1-\frac{1-i}2z\end{cases}\quad$ starting from the two points 0 and 1. The ...
3
votes
3answers
57 views

Recursion relation: Number of series length n made of $(0,1,2)$ so that each pair sum is between 1 and 3. [including them].

Recursion relation: Number of series length n made of $(0,1,2)$ so that each pair sum is between 1 and 3. [including them]. So what i did was: Let $a_n$ be the total number of series length n so ...
2
votes
5answers
191 views

Solving the recurrence relation [closed]

I'm interested in learning how can we solve this linear non-homogeneous recurrence relation? $$a_z = 2a_{n-1} - 1a{n-2} + (s^2 + 1)$$
1
vote
2answers
56 views

Finding the kth term of an iterated sequence

The sequence $x_0, x_1, \dots$ is defined through $x_0 =3, x_1 = 18$ and $x_{n+2} = 6x_{n+1}-9x_n$ for $n=0,1,2,\dots\;$. What is the smallest $k$ such that $x_k$ is divisible by $2013$?
2
votes
3answers
48 views

Using recurrence relation: How many n length series using [0,1,2] the sum of each pair is 3 at the most.

Using recurrence relation: How many n length series using [0,1,2] the sum of each pair is 3 at the most. Analyzing the question means that the pair (2,2) where-ever it appear is making the problem. ...
4
votes
3answers
74 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 ...
1
vote
1answer
91 views

A recurrence relation with words, contest type problem

For a positive integer $n$, a $n$-word is a string of $n$ letters, where each letter is an $A$ or $B$. Let $p_n$ be the number of $n$-words not containing four consecutive $A$ and not containing three ...
5
votes
4answers
513 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) ...
1
vote
1answer
108 views

How many times can a student skip class in a 14 weeks semester?

In a 14 weeks semester there are 5 school days each week. Johnny chooses each day if he goes to the University or skips the day. In how many ways can Johnny choose his attendance during the semester ...
2
votes
1answer
69 views

How to prove and derive coefficients that an exponential whose base decreases exponentially is a parabola

Suppose I have a function defined by this recurrence-relation: $$R(0) = r$$ $$R(n) = R(n-1) * (1+G)d^{n-1}$$ Here r is a base value, G is a base growth rate (G>0) and d is a decay in the growth rate ...
1
vote
3answers
106 views

HOW TO: Recurrence Relation $T(n) = 2T(n^\frac{1}{2}) + c$

I've been trying to do this for hours. I just don't know how. I'm familiar with recurrence relations in the form of $T(\frac{n}{2})$, but what do you need to do to solve $T(n^\frac{1}{2})$? I've ...
2
votes
2answers
447 views

Recurrence Relation for Strassen

I'm trying to solve the following recurrence relation (Strassen's):- $$ T(n) =\begin{cases} 7T(n/2) + 18n^2 & \text{if } n > 2\\ 1 & \text{if } n \leq 2 \end{cases} ...
1
vote
2answers
109 views

Recurrence equation

Given the following recurrence equation: $T(n)=T\left(\dfrac{n-1}{2}\right)+2$ , $T(1)=0$ How would you set this equation up in order to allow you to solve it using telescoping? Thanks in advance.
2
votes
3answers
101 views

Solution to Recurrence Relation

I asked a question previously, about how to describe $$ f(n) = n^3 $$ As a recurrence relation. I was, quite rightly, given $a_1=1$ and $a_{n+1}=a_n+3n^2+3n+1$. I have attempted to solve it, using ...
2
votes
2answers
86 views

Expressing a sequence as a recurrence relation

I've been working on a project, and it's come to that time when I have to prove the run time complexity of an algorithm. I've obtained my metric and those things that have nothing to do with you guys! ...
1
vote
2answers
36 views

Recursive formulae involving a linear operator

Given a basis $e_{1}$, $e_{2}$ in the plane, define the linear operator $F$ as $F(e_{1})=3e_{1}+e_{2}$ and $F(e_{2})=e_{2}$. Furthermore, define the sequence $u_{1},u_{2},\dots$ of vectors in the ...
0
votes
1answer
63 views

Solve the recurrence $T(n) = T(\log_2 n) + 13n$

I have the following recurrence relation $$T(n) = T(\log_2 n) + 13n.$$ I believe in order to solve the equation I need to determine the height of the tree. $$T(n) \to T(\log_2 n) \to ...
7
votes
1answer
103 views

Another recurrence… $T(n)=\sqrt{2n} \cdot T(\sqrt{2n}) + \sqrt{n}$

I'm trying to solve the following recurrence : $$T(n)=\sqrt{2n}\cdot T(\sqrt{2n}) + \sqrt{n}$$ I've tried substituting $n$ for some other variables to transform the above to something easier without ...
7
votes
1answer
47 views

Recurrence $u_{n+1}u_{n-1}-u_n^2=Ar^{n-1}$

I was going through some old puzzles and encountered one where there was a non-linear recurrence of form $$u_{n+1}u_{n-1}-u_n^2=Ar^{n-1}$$ with $u_0$ and $u_1$ given. I know I can use a test form ...
1
vote
2answers
97 views

Why do we substitute $\alpha^n$ in the recurrences of the form $ax_n=bx_{n-1}+cx_{n-2}$?

I encountered the following recurrence relation $2x_n-3x_{n-1}+x_{n-2}=0$ with $x_0=1$ $x_1=1$.I did not have any idea how to go about this.However, google pointed me to page 18 of Herbert Wilf's ...
1
vote
1answer
179 views

An issue with approximations of a recurrence sequence

By trying to give an approximation to a given recurrence sequence I encountered a problem. To be more precise I have a method but it fails if the right condition is not met and I wonder how I should ...
15
votes
5answers
692 views

limit of : $a_{n+2} =\frac{1}{a_n} + \frac{1}{a_{n+1}}$

$a_n$ is a real sequence, $a_1,a_2$ are positive and for all $n>2$ : $$ a_{n+2} =\frac{1}{a_{n+1}} + \frac{1}{a_{n}}.$$ Prove that: $\displaystyle \lim_{n\to \infty} a_n$ exists, then find it. ...
6
votes
3answers
311 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 ...
0
votes
1answer
131 views

How to express this recurrence relation as a closed form?

I need a little help with expressing this recurrence relation as a closed form. I've already expanded it out to see the pattern: $$ f(n) = f\left(\frac{n}{3}\right) + f\left(\frac{2n}{3}\right) + n - ...
0
votes
1answer
16 views

$A_k\leq C [2^{2k}A_{k-1}]^{\mu+1}, \ k=0,1,…$ implies $A_k\to 0$?

Consider the nonlinear recursive relation $$A_k\leq C [2^{2k}A_{k-1}]^{\mu+1}, \ k=0,1,...$$ where $C,A_k,\mu>0$. How can one show that if $A_0$ is small, then $A_k\to 0$? Thanks.
0
votes
2answers
63 views

Equation of a curve whose difference in ordinate values form an arithmetic sequence

I have the following recurrence equation that I have obtained while trying to solve a problem:- $$T(0) = 1$$ $$T(n) = T(n-1) + 9n - 8: n \ge 1$$ The values of $T(n)$ for $n = 0,1,2,... $ are as ...
2
votes
3answers
706 views

Solving recurrence equation using exponential generating functions

The recurrence is $ a_n = (n-1) a_{n-1} + (n-2)a_{n-2} $ I tried using exponential generating functions and have problems with it (the second term mostly) Further can this be solved without ...
1
vote
3answers
94 views

How to solve linear recurrences consisting of both $x_n$ and $y_n$?

I know how to solve a general linear, homogenous recurrence but these are the ones I've been given:(i) $x_{n+1} = 3x_n + 6y_n$(ii) $y_{n+1} = 6x_n - 2y_n$ Initial conditions: $x_0 = -1, y_0 = 0$ How ...
3
votes
2answers
93 views

Strong Mathematical Induction: Prove $3\mid b_n$ for a given recurrence relation $b_n$

Here is what I have so far: Proof $3\mid b_n$ for $n$ integers $\geq 1$ Base Cases both given $b_1=3, b_2=9$ and $b_n=6b_{n-2}+b_{n-1}$ $$P(1)=3\mid b_1$$ $$P(1)= 3\mid 3$$ Since $3\mid 3$, the ...
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}$
0
votes
1answer
112 views

Recurrence equation with upper and lower boundary condition

A very natural set up for recurrence equations is the following: $$ s(0) = 0 $$ $$ s(k) = A \ s(k-1) + B $$ $$ s(M) = A \ s(M-1), $$ where $0 \le A,B \le 1$ and $0 < k < M$. We can omit the ...
1
vote
1answer
252 views

Generalized Josephus problem

I have been reading generalized Josephus problem from Concrete Mathematics. The recurrence form for the problem is given as f(1) = a f(2n) = 2f(n) + b, for n >= 1 f(2n+1) = 2f(n) + y, for n >= 1 ...
1
vote
3answers
322 views

Strings and Substrings

So here is one of the last homeworks we are doing in my Discrete math class. It seems like it should be simple but I am really stuck. Any help would be greatly appreciated. Find the ordinary ...
1
vote
1answer
85 views

Convergence of $x_n=\sqrt{2(x_{n-1}-\log(1+x_{n-1}))}$

$x_n=\sqrt{2(x_{n-1}-\log(1+x_{n-1}))}$ with $x_0=a\ge0$ I calculated some values for $x_n$ with $a=0,1,2$ and recognized its monotonically decreasing (It converges to $0$). Now the standard approach ...
0
votes
1answer
23 views

Upper Bounds of Two Interdependant Recursive Sequences

For a pair of real numbers $\alpha$ and $\beta$, I need to prove that for the sequences $a_n = (-\alpha)a_{n-1} +b_{n-1}$ $b_n = (-\beta)a_{n-1}$ an upper bound exists with a form similar ...
0
votes
1answer
43 views

Master Method and use cases

$T(n)=T(n-2)+n^{2}$ and $T(n)=4T(n-2)+n^{2}$ Master method to solve these two equations? I know I can use the other cases where $a$ and $b > 0$ but since $T(n-2)$ do I assume $b$ is $1$?
0
votes
1answer
79 views

Rules Regarding Particular Solutions for Recurrence Relations

Suppose I have the recurrence relation $a_n = - a_{n-1} + a_{n-2} + 2^n + n$ Is it alright to solve for the homogeneous 'general' solution and then split the solving of the particular solution into ...
3
votes
1answer
384 views

why must orthogonal polynomials each have distinct roots?

Let $\langle\cdot,\cdot\rangle$ be any inner product on the set of functions $[a,b]\rightarrow\mathbb{R}$, and let $(p_n)_{n\in\mathbb{N}}$ be a sequence of polynomials defined by: $p_{-1}(x)=0$, ...
2
votes
5answers
270 views

Deriving Closed Form for a Recursion via Generating Functions

Consider (1) $a_{n+2} = 2a_{n+1} - a_n + 4n3^n$ with $a_0 = a_1 = 1$. Using generating functions and setting $A(x) = \sum a_nx^n$ we obtain $$\begin{align*}&\quad\sum a_{n+2}x^{n+2} = ...