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

learn more… | top users | synonyms

1
vote
1answer
21 views

Using recursion tree to solve recurence T(n) = 3(n/2)+n

I am trying to solve the recurrance of the function, T(n) = 3(n/2)+n where T(1) = 1 and show it's time complexity. n can be ...
-1
votes
1answer
18 views

Is master theorem applicable to the recurrence relation $T(n) = T(n/2)$?

Is master theorem applicable to the recurrence relation $T(n) = T(n/2)$? I do not think it applies because there no $n$ term and there is no $n^k$ for a $k$ which would equal $0$.
0
votes
1answer
34 views

Recursion and divisibility by $2^n$

A team plays a series of games, each of which results in either a win (W), a draw (D), or a loss (L). Let $S_n$ denote the number of possible sequences for a team which never loses two successive ...
1
vote
1answer
23 views

Solve the recurrence relation $x_{n+2} -3x_{n+1} + 2 x_n = n$

Solve $$x_{n+2} -3x_{n+1} + 2 x_n = n$$ when $x_0 = 1$ and $x_1 = 0$. I started with the homogen solution: $$r^2 -3r +2 = 0$$ So $$x_n^h = A1^n + B2^n$$ I know that $x_n = x_n^p + x_n^h$ But I ...
1
vote
1answer
995 views

Legendre polynomials recurrence relation

How can i get? $$P_{n+1}=xP_n(x)-\frac{1-x^2}{n+1} P'_n(x)$$ $n>=0$ Also know as the leadder equation of the legendre polinomials i tried to use de recurrence relations as: ...
5
votes
1answer
185 views
+100

Compute limit of the sequence $x_n$

Let $(x_n)$ be a real sequence such that $x_0=a\in\mathbb{R},x_1=b\in\mathbb{R},x_{n+2}=-\dfrac{1}{2}\left(x_{n+1}-x_{n}^2\right)^2+x_{n}^4\;\forall n\in\mathbb{N} $ and $|x_n|\leq ...
1
vote
1answer
20 views

Getting recursive formula to since solution

Is there any way to get the recursive formula of the form $r_n=\alpha r_{n-1}+\beta$ to single formula as a function of $n$. I've seen results that find single formula as function of $n$ for geometric ...
-4
votes
0answers
14 views

Solving following recurrences [on hold]

Find the asymptotic order of the following recurrence, represented in big-theta notation $$A(n) = 4A\left(\frac{n}{2}+5\right)+n^2$$ $$B(n)= B(n-4)+ \frac{1}{n}+\frac{5}{n^2+6}+\frac{7n^2}{3n^3+8}$$ ...
1
vote
1answer
34 views

Applying the master theorem

State the asymptotic runtime found by the master theorem. If the master theorem does not apply state why: 1) $T(n) = $T($n/3)$ 2) $T(n)= $ $5T$($2n/5$) + $n$ 3) $T(n) = 4T(n/2) +15n^3 + 4n^2 +n+4$ ...
0
votes
0answers
11 views

Can Banach fixed-point theorem be generalized to the case where each term depends on multiple previous terms in recurrence sequence

Banach fixed-point theorem http://en.wikipedia.org/wiki/Banach_fixed-point_theorem I'm wondering if the theorem still applies if the recurrence relation is, for example, ...
0
votes
1answer
37 views

proving a sequence is increasing defined by a recurrence relation.

Given the recurrence relation $b_{1}=0$ and $$3b_{n+1} = \frac{b_{n}}{12} + \sqrt{\frac{17+b_{n}^{2}}{12}}$$ Show that this recurrence relation is increasing. Note $36b_{n+1} = b_{n} + ...
2
votes
0answers
35 views

How to calculate alternating Euler sum [on hold]

In How to calculate $\sum_{n=1}^\infty\frac{(-1)^n}n H_n^2$? get $$\sum_{n=1}^\infty\frac{(-1)^n}n H_n^2=\frac{1}{12}(\pi^2\log2-4(\log 2)^3-9\zeta(3)),$$ Similar, how to evaluate the series, ...
0
votes
2answers
19 views

recurrence problem for number of words

Let $w_n$ be the number of words (strings) of length $n$ that can be made using the digits {0,1,2,3} with an odd number of twos. Find a recurrence relation for $w_n$ and solve the recurrence. The ...
0
votes
1answer
41 views

Finding recurrence relation on a problem

I need a little bit help finding a recurrence relation. So it goes like this: "A one-sided pavement is being made with tiles that come in 5 different colors. There are 3 light colors (light-yellow, ...
0
votes
0answers
13 views

What is the growth of $T(n)=aT\left(\left\lfloor\sqrt[k]{n}\right\rfloor\right)+b\log(n)$

What is the growth of $T(n)=aT\left(\left\lfloor\sqrt[k]{n}\right\rfloor\right)+b\log(n)$ where $a$ and $b$ are positive reals and $k \ge 2$ is an integer? This is a generalization of my answer to ...
2
votes
2answers
56 views

Find recurrence relation of $T(n)=2T\left(\left\lfloor\sqrt{n}\right\rfloor\right)+\log(n)$

Sorry about the formatting of the title I'm not sure of the codes to make it look better. I need to find the recurrence relation of the following: $$T(0) = 1$$ $$T(n) = ...
1
vote
0answers
31 views

Non-recursive closed-form of the coefficients of Taylor series of the reciprocal gamma function

The reciprocal gamma function has the following Taylor series. $$\frac{1}{\Gamma(z)}=\sum_{k=1}^{\infty}a_kz^k,$$ where the $a_k$ coefficient are given by the followint recursion. $a_1=1$, ...
5
votes
2answers
39 views

A nice recurrence sequence

I want to find general solution for recurrence: $a_n=7a_{n-1}-10a_{n-2}+4n$ with suppose $c_1, c_2, c_3$ is constant. I need some tutorial or solution on this challenging recurrence.
1
vote
4answers
81 views

Prove sequence is Cauchy.

Prove the sequence $\{a_i\}$ defined by $a_1=1 \text{ and } a_{i+1} = 1 + \frac{1}{a_i}$ is Cauchy. And prove it converges to $\sqrt{2}$. I want to show $\lim\limits_{n\to\infty}(a_{i+1}-a_i)=0$ for ...
4
votes
1answer
115 views

After how many steps can compositions of $x\mapsto x+1$ and $x\mapsto x^2+1$ produce the same result starting from $1$ and $3$?

This problem is from a Turkish contest: Let $P(x)=x+1$ and $Q(x)=x^2+1$. Consider all sequences $(x_k,y_k)$ such that $(x_1,y_1)=(1,3)$ and $(x_{k+1},y_{k+1})$ is either $(P(x_k),Q(y_k))$ ...
1
vote
0answers
28 views

Complicated 2-variable recurrence

I am analyzing some kind of construction for which size satisfies the following recursion: $P(n,k)=\frac{k}{2}\log \frac{k}{2} + 1 + \frac{n}{2} + P(\frac{n}{2},k) + P(\frac{n}{2},\frac{k}{2})$ ...
1
vote
1answer
29 views

Solving recurrence equations with repeated substitution?

Say we have a recurrence equation as $$ T(n) = \begin{cases} T\left(\frac n2\right) +n & \text{if }n\ge2 \\ 1 & \text{if }n=1 \end{cases} $$ Would the first substitution be like this? ...
19
votes
1answer
374 views

Infinite staircase to a circle

Suppose you start at $(0,0)$ on the unit disc and repeat the following procedure again and again: Face east and walk half-way to the circumference. Face north and walk half-way to the circumference. ...
2
votes
1answer
36 views

Solving recurrence -varying coefficient

How can one find a closed form for the following recurrence? $$r_n=a\cdot r_{n-1}+b\cdot (n-1)\cdot r_{n-2}\tag 1$$ (where $a,b,A_0,A_1$ are constants and $r_0=A_0,r_1=A_1$) If the $(n-1)$ was not ...
0
votes
1answer
42 views

Limit of a sequence defined by recursive relation : $ a_n = \sqrt{a_{n-1}a_{n-2}}$

We're given a sequence defined by the recursive relation: $$a_n = \sqrt{a_{n-1}a_{n-2}}$$ $a_1$ and $a_2$ are positive constants. We have to show the following: The sequences $\{ b_n \} = \{ ...
0
votes
3answers
25 views

This recurrence relation will evaluate to?

T(n) = 2T(n-1)+n, n>=2 T(1) = 1 What will this recurrence relation equation evaluate to ? I used substitution method and found out that this relation takes the form 2^k T(n-k) + 2^(k-1) * ...
1
vote
0answers
18 views

Solving a recurrence with a term $T(\frac n 2 + 2)$

I'm stuck trying to solve the following recurrence: $$\begin{align*} T(n) &= 4T(\frac n 2 + 2) + n : n > 8\\ T(n) &= 1 : n \leq 8 \end{align*}$$ In particular, I'm not sure how to deal ...
0
votes
0answers
3 views

About Laguerre Recurrence Relation from Gram-Schmidt

I wonder how to deduce Laguerre Recurrence Relation from Gram-Schmidt onthogonalization process applied to the monomial basis Thanks
3
votes
4answers
84 views

Recurrence relation $x_0=1, x_n=p x_{n+1} + q x_{n-1}$

I have the following recurrence relation: $$x_0=1 \\ x_n=p x_{n+1} + q x_{n-1} \text{ for }n=1,2,3,...$$ where $0<p=1-q<1$ and $0 \leq x_n \leq 1$. Edit: Sorry for the lack of context. But I ...
0
votes
2answers
505 views

Using recurrences to solve $3a^2=2b^2+1$

Is it possible to solve the equation $3a^2=2b^2+1$ for positive, integral $a$ and $b$ using recurrences?I am sure it is, as Arthur Engel in his Problem Solving Strategies has stated that as a method, ...
0
votes
1answer
39 views

Recurrence relation taken to infinity [closed]

Very simple question.... Say we have a recursive function: $x_n = \dfrac{c}{2ax_{n-1}}$ where $x_0 \in \mathbb Z^+$ and $n \in \mathbb Z^+$ ($x_n \in \mathbb Z^+$, for now, but this should work ...
1
vote
1answer
53 views

Help with using Master Theorem on $T(n)=9T(n/3) + \Theta(n^2/\operatorname{lg}(n))$

I want to use the Master theorem to solve the following recurrence. $$T(n)=9T(n/3) + \Theta(n^2/\operatorname{lg}(n))$$ We can easily see that $a=9$ and $b=3$ and $f(n) = n^2/\operatorname{lg}(n)$. ...
0
votes
0answers
8 views

Developing closed-form from recursive definition

Here is a recursively-defined function where c, d ∈ N. T(n) =    c, if n = 0 d, if n = 1 2T(n − 1) − T(n − 2) + 1, if n > 1 Carry out the five steps for repeated substitution to prove a ...
0
votes
1answer
31 views

Help with using Master Theorem on Floor/Ceiling Functions [closed]

I have to use the master theorem to find the asymptotic growth of this function in Big-theta notation. T(x) = T(⌈x/4⌉) + T(⌊x/4⌋) + √x How should I approach this ...
0
votes
1answer
16 views

Substitution method for solving recurrences piece wise function

I don't know how to use the substitution method for the following function: piece wise function: $T(n) = c$, if $n=0$ $T(n) = d$, if $n=1$ $T(n)=2T(n-1)-T(n-2)+1$, if $n > 1$
1
vote
3answers
31 views

Showing that a sequence $a_n$ is a solution of the recurrence relation

I'm having some trouble with showing that a sequence $a_n$ is a solution to the recurrence relation $a_n = -3a_{n-1} + 4a_{n-2}$. (See image below). The sequence $a_n$ that is given $= (-4)^n$ . I'm ...
0
votes
0answers
18 views

Recurrences with modulo

Is there any specific way to solve recurrence of form (example): $$f(x) = (a \cdot f(x-1) + c) \bmod{r} $$ (when recurrence involves modulo). For recurrence without modular arithmetic I could use ...
1
vote
2answers
60 views

Determine whether $A215928(n)=G_n$.

Let $G_0=1$ and $G_{n+1}=F_0G_n+F_1G_{n-1}+\cdots+F_nG_0$, where $F_n$ is the $n$th term of the Fibonacci sequence, i.e., $F_0=F_1=1$ and $F_{n+1}=F_n+F_{n-1}$. Let $P_0=P_1=1,\ P_2=2,$ and ...
1
vote
4answers
56 views

Is this recursively defined sequence decreasing? $x_{n+1}={1\over{4-x_n}}$, $x_1=3$.

This is part of a larger problem: Prove that the sequence defined by $x_1=3$, $x_{n+1}={1\over{4-x_n}}$ converges. I want to show that it is bounded below (by $0$ or something) and that it is ...
1
vote
1answer
1k views

Solve the Relation $T(n)=T(n/4)+T(3n/4)+n$ [closed]

Solve the recurrence relation: $T(n)=T(n/4)+T(3n/4)+n$. Specify the best asymptotic running time.
6
votes
1answer
212 views

Recursion relation of fourth order Runge-Kutta method applied on system

I'm trying to apply the Gauss-Legendre method of fourth order (as Runge-Kutta method) on the following system of equations $$\left\{ \begin{matrix} \dot{a} =& -b \\ ...
1
vote
0answers
96 views

Method for deriving an Exponential Moving Average?

I have a formula for an exponentially weighted moving average function defined recursively as: $S_t = a*Y_t+(1-a)*S_{t-1}$ Where: $a\in (0,1)\cap \mathbb{Q}$ $t$ represents time $Y_t$ is the value ...
1
vote
2answers
21 views

How to analyze convergence of non-linear difference equation (recurrrence relations)

I've a couple of functions, such as: $Y(t+1)=2-\ln(Y(t))$ $Y(t+1)=(Y(t))^{-2}$ $Y(t+2)=e^{-Y(t)}$ and I need to analyze stability and convergence. No problem with stability, but I can't figure out ...
2
votes
3answers
116 views

Recurrence relation problem

If $a$ is a sequence defined recursively by $a_{n+1} = \frac{a_n-1}{a_n+1}$ and $a_1=1389$ then can you find what $a_{2000}$ and $a_{2001}$ are? it would be really appreciated if you could give me ...
1
vote
1answer
25 views

Dynamic Programming - how to minimize sum of distances

Let's assume that we're given the num[N], an array of N positive integers in an ascending order. For instance, let's assume that N=10, and num[N] is the following: 1 2 3 6 7 9 11 22 44 50 Let ...
3
votes
0answers
28 views

How to work with a recursive function with 2 recursive instances?

In class, we figured out how to find the closed form of a recursive definition through the "basic 5 steps method". Example function T(n): If n = 1, T(1) = 1 If n > 1, T(n) = T(n-1)+1 Step 1: ...
1
vote
2answers
31 views

How do I solve this recurrence relation?

Given a recursive relation $$a_n = \begin{cases} (1 - 2b_n)a_{n-1} + b_n, & n > 1 \\ \frac{1}{2}, & n =1 \end{cases} $$, how can I expression $a_n$ in term of $b_i, i \in \{1, 2, \dots ...
1
vote
1answer
20 views

Checking recurrence relation

Is there a way to check my recurrence relation, so I can confirm I did it correctly? $a_k = -4a_{k-1} -4a_{k-2}$ with $a_0 = 0$ $a_1= -1$ My answer: $a_n = 0(-2)^n - ½n(-2)^n$
1
vote
1answer
31 views

How do I use complete induction here?

Suppose currency consists of 3 and 4 cent coins. Suppose you want to buy an item that is worth 9 cents. Show that if you have an unlimited number of 3 and 4 cent coins you can buy anything greater ...
0
votes
0answers
13 views

Maxima of a recurrence

The following recurrence has a maxima around $k = \lceil \log_d{n}\rceil$, where $n > 0$, $d > 3$: $$b(n,k) = {b(n-1,k-1)\over {d^{k-1}}} + (1-{1\over {d^{k}}})b(n-1,k)$$, where $0 \le k \le ...