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

learn more… | top users | synonyms

-2
votes
0answers
22 views

generating function for given sequence [on hold]

I am new to generating function.Can anyone please describe the process to find the generating function for given sequence? ...
2
votes
1answer
33 views

Repeated substitution gone wrong

It was an exam question. $$ f(n)= \begin{cases} 0 & \mbox{if } n \leq 1 \\ 3 f(\lfloor n/5 \rfloor) + 1 & \mbox{if } n > 1 \\ \end{cases}$$ So by calculating some I have $f(5) = 1$, $f(10) ...
0
votes
2answers
24 views

Prove that a sequence of recursive functions $\,f_n(x)$ cannot converge pointwise to $\,f(x)$ on $[0,1]$

Given a recursive sequence $\,f_n(x) :[0,1] \to \mathbb R$, $x \in [0,1]$, where $$\begin{align*} f_1(x) &= x, \\[6pt] f_n(x) &= \frac{2x\,f_{n-1}(x)}{n!} \end{align*}$$ I have proven that the ...
1
vote
0answers
23 views

Recurrence Derivative

I have a recurrence relation as follows $ \left\{ \begin{array}{ll} R_0=H & \mbox{if } n = 0 \\ R_1(s)=sR_0 \hspace{.1cm} A & \mbox{if }n=1\\ R_{n+2}(s)=\frac{s}{n+2}\{ ...
1
vote
0answers
30 views

What does “combining the solutions in O(n) time” mean?

Algorithm $X$ proceeds by recursively solving $5$ subproblems of one-half the size, then combining the solutions in $O(n\log n)$ time. Algorithm $Y$ makes $9$ recursively calls on ...
0
votes
1answer
33 views

How to quickly determine running time of such recurrence relations?

$$T(n)=5T(\frac{n}{2})+n\log n$$ $$T(n)=9T(\frac{n}{3})+n^2$$ $$T(n)=2T(\frac{2n}{3})+n^{1.5}$$ What are the running times of each $T(n)$? Each one looks like the form of the Master Theorem, but only ...
0
votes
0answers
21 views

How to solve these recurrences

I have this recurrence and I have tried to solve it but I am completely lost. Master Theorem cannot be applied on this at-least not without some substitution or stuff. $ i)\quad T(n) = 4 T( \left ...
0
votes
2answers
27 views

Solve the recurrence $T(n)=3T(n/3)+\log n$, $T(1)=1$

So $T(n)=3T(n/3)+\log n$ and $T(1)=1$. I tried to solve this by expanding it out to see a pattern, but I don't really see the pattern: $T(n/3) = 3T(n/9)+\log (n/3)$ $T(n) = 3[3T(n/9)+\log ...
1
vote
1answer
8 views

Using a recursion tree to obtain an algorithm classification with n^2 time

I'm having trouble getting the classification of this recurrence relation using a recursion tree. $$T(n) = 3T(n/2) + n^2$$ I have the tree written out correctly (I hope): ...
2
votes
1answer
26 views

Imaginary solutions of a recurrence relation

How to solve this recurrence relation using characteristic equation and imaginary numbers? We have $a_0 = 0$ and $a_1 = 1$ , and for all $j\in\mathbb N$: $$a_{j+2} = 6a_{j+1} - 10a_j$$ I would ...
0
votes
2answers
53 views

Clueless when solving recurrence relations

I really need some help solving recurrence relations in a relatively quick manner, so any insight would be highly appreciated. Here are a few of the ones on my midterm sample that I'm struggling with: ...
0
votes
3answers
43 views

Solve recurrence relation problem

This is a recursion problem that I am stuck at. I need to use the characteristic equation. Let $a_0, a_1, a_2, . . .$ be defined by $a_0 = 5, a_1 = 0$, and $a_{n+2} = a_{n+1} + 6a_n$ for $n \ge 0$. ...
0
votes
2answers
24 views

What's the procedure for solving recurrence relations without coefficients?

I've a recurrence relation $$a_{2n}=(2n-1) a_{2n-2}$$ (intial condition $a_2 = 1$) which has no coefficients, so I can't follow the standard procedure where I find the roots from which we ...
0
votes
0answers
21 views

Recurrence relations and their solutions

I recently read an article about difference equations and found the solution of the fibonacci recurence there. It is this function: $f(n) = \frac{1}{\sqrt5}\left (\frac{1+\sqrt5}{2} \right )^{n}- ...
1
vote
0answers
59 views

What is the recurrence relation between $a_n, a_{n-1}$ , $a_n = \int_0^1 {x^n}\tan\left( \frac{\pi}{4}x\right) dx$

I would appreciate if somebody could help me with the following problem Q: What is the recurrence relation between $a_n, a_{n-1}$ ? $$ a_n = \int_0^1 {x^n}\tan\left( \frac{\pi}{4}x\right) dx,\ \ ...
0
votes
2answers
34 views

Solving recurrence with non constant coefficients

I am having a hard time to solve the following $a_k=\left(\frac{d}{2}\right)^{k-2}a_{k-2}$ where $d$ is a parameter and $a_0=1$ $a_1=d$. Will appreciate your help. Thanks!
0
votes
3answers
52 views

Showing the divergence of the series where $a_1 = 2$ and $a_{n+1} = \frac{5n+1}{4n+3}a_n$.

Consider a series such that its $i$th term $a_i$ is defined by $a_1 = 2$ and $a_{n+1} = \dfrac{5n+1}{4n+3}a_n$. I would like to show that this series is divergent. Here's how I thought about it: ...
1
vote
1answer
37 views

What type of series is this: $k^n + k^{n-1} + k^{n-2} + k^{n-3}+\dots$

I am wondering what type of series this this, where you have some constant (let's say 4) to the power of n, summed up where each new exponent keeps going $n-1, n-2, n-3, n-4, ...$ and so on. So, ...
1
vote
1answer
25 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 ...
0
votes
1answer
28 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$.
1
vote
1answer
49 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 ...
0
votes
1answer
35 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 ...
0
votes
0answers
11 views

Prove that the row sums of $T$ satisfy the following formula.

Consider the lower triangular matrix defined by the recurrence: $$T(n,1) = 1$$ $$\text{If}\; n\geq k \; \text{then} \; T(n,k) = \sum _{i=1}^{n-1} T(n-i,k-1)+y \sum _{i=1}^{n-1} T(n-i,k) \; ...
1
vote
1answer
22 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
15 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
12 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
38 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
39 views

How to calculate alternating Euler sum [closed]

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
26 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
0answers
15 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
60 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
35 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$, ...
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 ...
5
votes
2answers
43 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
0answers
31 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? ...
0
votes
1answer
43 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 \} = \{ ...
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
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
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
35 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 ...
1
vote
1answer
56 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)$. ...
3
votes
4answers
88 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
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$
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
61 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
57 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 ...