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

learn more… | top users | synonyms

1
vote
2answers
126 views

$a_{n+1}=\frac{1}{2}\left(a_n+\frac{1}{a_n}\right)(n=1,2,3,\cdots),~a_1=2$

I would appreciate if somebody could help me with the following problem: Q: find $a_n=?$ $$a_{n+1}=\frac{1}{2}\left(a_n+\frac{1}{a_n}\right)(n=1,2,3,\cdots),~a_1=2$$
1
vote
3answers
1k views

$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer

$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer, need help, I dont know how to solve it?
1
vote
4answers
73 views

Solving the recurrence relation $a_{n+1}=a_n^2$

How would one solve the recurrence relation $a_{n+1}=a_n^2$ for, say, $a_0=2$? The solution seems to be $a(n)=2^{2^n}$, but how would one get to that conclusion? Furthermore, how would one solve a ...
1
vote
3answers
68 views

recurrence relation expanding $ij$

I need to solve this: $\displaystyle\sum\limits_{i=1}^n$$\displaystyle\sum\limits_{j=1}^n $$\displaystyle\sum\limits_{k=1}^{i\cdot j} 1$ How do I expand the $i\cdot j$ part? Am I right to do it this ...
1
vote
4answers
2k views

Solve the recurrence $T(n) = 2T(n-1) + n$

Solve the recurrence $T(n) = 2T(n-1) + n$ where $T(1) = 1$ and $n\ge 2$. The final answer is $2^{n+1}-n-2$ Can anyone arrive at the solution.
1
vote
4answers
358 views

Solving a recurrence of polynomials

I am wondering how to solve a recurrence of this type $$p_1(x) = x$$ $$p_2(x) = 1-x^2$$ and $$p_{n+2}(x) = -xp_{n+1}(x)+p_{n}(x).$$ I am wondering, how could one solve such a recurrence. One way ...
1
vote
5answers
582 views

How to get the characteristic equation?

In my book, this succession defined by recurrence is presented: $$U_n=3U_{n-1}-U_{n-3}$$ And it says that the characteristic equation of such is: $$x^3=3x^2-1$$ Honestly, I don't understand how. ...
1
vote
2answers
87 views

Recurrence relation $T_{k+1} = 2T_k + 2$

I have a series of number in binary system as following: 0, 10, 110, 1110, 11110, 111110, 1111110, 11111110, ... I want to understand : Is there a general seri ...
1
vote
3answers
51 views

Solve recurrence equation

Could you Show me how to solve this equation: $$x_n = \sqrt2x_{n-1} + \sqrt3$$ for $n \ge 1$ with $x_0 = 1$.
1
vote
4answers
371 views

What is generally the strategy for converting recurrence to closed form?

Consider the Fibonacci sequence (as an example) \begin{align*} f(n) &= f(n-1) + f(n-2) \\ f(0) &= 0\\ f(1) &= 1 \end{align*} How do you convert this to the closed form ...
1
vote
6answers
107 views

limit of convergent series

What is the limit of $U_{n+1} = \dfrac{2U_n + 3}{U_n + 2}$ and $U_0 = 1$? I need the detail, and another way than using the solution of $f(x)=x$, as $f(x) = \frac{2x+3}{x+2}$ because I can't show ...
1
vote
3answers
50 views

How does my professor go from this logarithm to the following one of a different base?

I don't understand on the second last line how my professor goes from $2^{log_3(n)} = n^{log_3(2)}$ how is that relation formed?
1
vote
3answers
281 views

How to solve recurrence equation $f(n) = f(n-5) + f(n-10)$?

How to solve recurrence equation $f(n) = f(n-5) + f(n-10)$? For something like fibonacci sequence $f(n+1) = f(n) + f(n-1)$ I can solve for the quadratic equation $x^2-x-1=0$ then $f(n) = A x_1 + ...
1
vote
2answers
329 views

solving inhomogeneous recurrence relation

I had encountered an inhomgeneous equation of the type : $$f(n)=h(f(n))+g(n)$$ below is the equation. $$f(n)=\begin{cases} f(n-1)+2^{(n-1)/2},&\text{if }n\text{ is odd}\\\\ ...
1
vote
2answers
535 views

Recurrence relations and Generating functions - how to find the initial conditions?

Best to ask by example. Given the recurrence relation $a_{n}=a_{n-1}+a_{n-2}$, and some given initial conditions, we can find a similar relation for the generating function for the sequence, ...
1
vote
2answers
46 views

How do we solve the exact recurrence for $T(1) = 1, T(n) = 3T(n - 1) + 2n + 2$ for $n > 1$?

This looks like an exponential recurrence due to the 3 behind $T$, but I'm not sure how to formally solve for $T(n)$ without $T$ on the righthand side.
1
vote
3answers
83 views

$W_n=\int_0^{\pi/2}\sin^n(x)\,dx$ Find a relation between $W_{n+2}$ and $W_n$

Set $$W_n=\int_0^{\pi/2}\sin^n(x)\,dx.$$ Compute $W_0$ and $W_1$. Find a relation between $W_n$ and $W_{n+2}$ and deduce a formula for $W_n$. What I have so far is: $$W_{2k}=\frac{1}{2^k}\left( ...
1
vote
3answers
75 views

Recurrence relations with fractions

I have the following two equations: $$\alpha(t)=\frac{a}{b+\beta(t-1)}\\ \beta(t)=\frac{c}{d+\alpha(t-1)}$$ where $a,b,c,d$ are constants. Question is, is there an analytical form for $\alpha$ as ...
1
vote
5answers
459 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 ...
1
vote
2answers
94 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
3answers
80 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 ...
1
vote
2answers
92 views

Solving Another Recursion Using Generating Functions

I am trying to find a closed form for $$ Y(n) = Y(n-1) -2Y(n-2) + 4^{n-2} \text{ with initial conditions } Y(0) = 2,Y(1) = 1 $$ using generating functions. However, I am still not entirely ...
1
vote
2answers
185 views

Solving a recurrence by using characteristic equation method

How can I solve $$T(n) = aT(n-1) + bT(n-2)+ cn $$; where $a,b,c$ are constants. I could not figüre it out :( There are T(0) = d and T(1) = e, Thanks in advance.
1
vote
3answers
35 views

Where is the error in finding the particular solution to this recurrence relation?

The question is to write the general solution for this recurrence relation: $y_{k+2} - 4y_{k+1} + 3y_{k} = -4k$. I first solved the homogeneous equation $y_{k+2} - 4y_{k+1} + 3y_{k} = 0$, by writing ...
1
vote
2answers
41 views

Closed form of $T(n)=T(\lceil n/2 \rceil)+T(\lfloor n/2 \rfloor)+2$

How in God's name could I find a closed form of $T(n)=T(\lceil n/2 \rceil)+T(\lfloor n/2 \rfloor)+2$? I'm looking at the first numbers in sequence and I just don't see any relation...
1
vote
4answers
64 views

How to solve this reccurence relation?

Let a,b,c be real numbers. Find the explicit formula for $f_n=af_{n-1}+b$ for $n \ge 1$ and $f_0 = c$ So I rewrote it as $f_n-af_{n-1}-b=0$ which gives the characteristic equation as $x^2-ax-b=0$. ...
1
vote
3answers
70 views

recurrence relation for squares of fibonacci numbers

I have a problem finding a proof that the squares of the Fibonacci numbers satisfy the recurrence relation $a_{n+3} - 2*a_{n+2} - 2*a_{n+1} + a_n = 0$ and solving this recurrence relation. Some help ...
1
vote
4answers
850 views

how to find nth term in a fibonacci series or sum of a series of fibonacci numbers

A series is given as $1,6,7,13,20,33,.......$ and so on Find the sum of first 52 terms? what i know is The sum of the first n Fibonacci numbers is the [(n + 2)nd Fibonacci number - 1] . So the sum ...
1
vote
2answers
62 views

Recurrence relation, generating function

I am trying to solve this recurrence relation using generating functions $$x_{n+2}+x_{n+1}+x_n=0$$ $$x_0 = x_1=1$$ I have got this generating function $f_a(x)=\frac{2x+1}{x^2+x+1}$. Since the ...
1
vote
2answers
60 views

Find the value of the the term

The sequence $a_1,a_2,a_3,\ldots$ satisfies $a_1=1$, $a_2=2$, and $$a_{n+2}=\frac2{a_{n+1}}+a_n\;;$$ find the value of $$\frac{a_{2012}2^{2009}}{2011}$$
1
vote
2answers
37 views

What is $f(t)=X_{t+1}$, if $X_{t+1}=(1-p)(1-X_{t})+pX_{t}$ and $X_{0},p \in [0,1]$?

What is $f(t)=X_{t+1}$, if $X_{t+1}=(1-p)(1-X_{t})+pX_{t}$ and $X_{0},p \in [0,1]$? And what are general methods for finding functions defined by such recurrent equations?
1
vote
4answers
142 views

Reccurence relation: Lucas sequence

I need to solve the given recurrence relation:$$L_n = L_{n-1} + L_{n-2},$$ $n\geq3$ and $ L_1 = 1, L_2 =3$ I'm confused as to what $n\geq3$ is doing there, since $L_1$ and $L_2$ are given I got ...
1
vote
3answers
130 views

How do you go about solving difference equations?

Say you have something of the form $p_1 = p$ $p_n=kp_{n-1}+(1-k)(1-p_{n-1})$ How does one go about finding $p_{n}$ in terms of $n,p$ and $k$? In my notes here's how it's found $p_n-1/2 = ...
1
vote
4answers
253 views

Generalized Fibonacci sequences

Why Fibonacci sequence start at $0$, Tribonacci sequence with $0,0$, Tetranacci with $0,0,0$, etc. [ref OEIS] Has any good reasons for that? These sequences arise in generalization of Pascal Triangle ...
1
vote
3answers
432 views

Finding characteristic equation of problem and solve recurrence relation

I have a homework assignment to find the characteristic equation of the set which a(n) = the number of sequences of length n which can be build from ${1,2,3...8}$ but you can't have two even numbers ...
1
vote
2answers
172 views

If $f(n) + (n+1)^2 = f(n+1)$ then what is $f\phantom{|}$?

Suppose that $$f(n) + (n+1)^2 = f(n+1),$$ How could I find the original (or family of) function(s) that satisfies this property? What is the branch of mathematics that deals with equations like ...
1
vote
1answer
23 views

Recurrence relation to calculate the number of strings of $n$ characters that don't have consecutive vowels.

How can I find a recurrence relation to calculate the number of strings of $n$ characters (english alphabet, lowercase) that don't have consecutive vowels. It's clear that for $n = 1$ the result is ...
1
vote
3answers
36 views

Strategies for developing explicit formulas for nth term given recurrence relation?

I'm wondering if there's any general strategies to develop an explicit formula for the nth term when you're given a recurrence relation. For example, I'm given a recurrence relation: $a_{n+1}=2a_n+1$ ...
1
vote
3answers
69 views

Still a novice could use a little help

Ok, so I have this question, and we never went over this or how to solve it in class. I can't find an example in the book either. How do I show that $f_n = 3^nA + 2^nB$ satisfies the recurrence ...
1
vote
1answer
29 views

Non-recursive way to present $ p_{0}=0$, $p_{n+1}=(e+1)p_{n}+e$ for some $e>0 \in \mathbb{R}$.

Is there a non-recursive way to present this function: $ p_{0}=0$ $p_{n+1}=(e+1)p_{n}+e$ for some $e>0 \in \mathbb{R}$. Or at least some estimation from the top would satisfy me.
1
vote
4answers
787 views

Find the limit of a recursive square root sequence.

Find the limit of the sequence $$\left\{\sqrt{2}, \sqrt{2\sqrt{2}}, \sqrt{2\sqrt{2\sqrt{2}}}, \dots\right\}$$ Another way to write this sequence is $$\left\{2^{\frac{1}{2}},\hspace{5 pt} ...
1
vote
2answers
89 views

How to solve $f_{n}(x)=xf_{n-1}(x)-f_{n-2}(x)$?

How to solve the following recurrence relation $$f_{n}(x)=xf_{n-1}(x)-f_{n-2}(x)$$ with the initial conditions $f_{1}(x)=x, f_{2}(x)=x^2-1$? The answer is that ...
1
vote
1answer
54 views

Prove by induction that $d_n=2^n+3^n$, where $d_n = 5d_{n-1}-6d_{n-2}$

I have one more induction question. $d_0 =2 $ $d_1=5$ let $d_n=5d_{n-1} - 6d_{n-2}$ Prove that $d_n=2^n+3^n$
1
vote
2answers
59 views

Recursion problem help

The following are the teachers example problems. The issue is that I don't understand the exact steps they took to go from $f(0)$ to $f(1)$ to $f(2)$ to $f(3)$. What I'm asking here is if someone ...
1
vote
1answer
220 views

numerically evaluate a continued fraction

I am looking at a continued fraction of the form $$ F_n = \cfrac{1}{1+\cfrac{p_1}{1+\cfrac{p_2}{1+\cfrac{p_3}{1+\ldots}}}} $$ where $p_n$ is a function I know. For simplicity I just take it to $p_n=n$ ...
1
vote
1answer
90 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 ...
1
vote
3answers
202 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
2answers
633 views

Solving a recurrence relation using master method

I know that the Master theorem is used for the recurrence relations of the form: $$T(n) = aT(n/b) + f(n)$$ In my question, I am supposed to solve the following recurrence relation by using Master ...
1
vote
2answers
88 views

What is the asymptotical bound of this recurrence relation?

I have the recurrence relation, with two initial conditions $$T(n) = T(n-1) + T(n-2) + O(1)$$ $$T(0) = 1, \qquad T(1) = 1$$ With the help of Wolfram Alpha, I managed to get the result of ...
1
vote
1answer
186 views

finding recurrence relations

This is homework, please only provide hints. I've been given a problem: consider a 1-by-n chessboard. Coloring each square with one of two colors, red or blue. Let $a_n$ be the number of colorings in ...