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

learn more… | top users | synonyms

0
votes
1answer
14 views

How to give a good guess the recurrence relation problem

I have been trying to solve the following recurrence relation $$T(n)=2T(\frac{n}{2}) + nlgn$$ by using substitution method. I started to compute $T(1)$ ,$T(4)$,$T(8)$,$T(16)$ to guess a solution as ...
1
vote
2answers
24 views

Show that a solution is the general solution.

Find general solution of recurrence relation $$ ax_{n+1}+bx_n+cx_{n-1}=0 $$ for two distinct roots $\alpha$ and $\beta$.. My question is: One solution is $y_n=A\alpha^n+B\beta^n$. But how ...
1
vote
3answers
24 views

General solution of recurrence relation if two equal roots

Consider the recurrence relation $$ ax_{n+1}+bx_n+cx_{n-1}=0 $$ If the characteristic equation $$ a\lambda^2+b\lambda+c=0 $$ has two equal roots, then the general solution is given by $$ ...
0
votes
1answer
16 views

Find all solutions of recurrence relation

For $p\in (0,1)$ and $q:=1-p$ find all the solutions $h=(h_i)_{i\in\mathbb{N}_0}$ of the recurrence relation $$ \begin{cases}h_0=1\\h_i=ph_{i+1}+qh_{i-1}, & \text{ for ...
3
votes
1answer
56 views

Proving that $\lim\limits_{n \to \infty} \frac{E_{n+1}}{E_n}=2^{-2/3}$

$$\def\ut#1{\underline{\text{#1}}}\def\vec#1{\mathbf{#1}} \def \d{\mathrm{d}} \def \p{\partial } \def \[{\left[} \def \]{\right]} \def \({\left(} \def \){\right)} \def \n{\boldsymbol{ \nabla}} ...
0
votes
3answers
32 views

Solving $ax_{n+1}+bx_n+cx_{n-1}=0$

In a book I found the following: Consider a recurrence relation of the form $$ ax_{n+1}+bx_n+cx_{n-1}=0 $$ where $a$ and $c$ are both non-zero. Let us try a solution of the form ...
0
votes
1answer
11 views

Recurrence Relation Theta bound

I have a recurrence of type T(n)T(n) = T(n/2)T(2n) − T(n)T(n/2) How to find a theta bound for T(n)?
0
votes
1answer
17 views

Solving inhomogenous first order difference equation (recurrence relation)

I have the equation (arising in a probabilistic context) $$ x_n = a(1-x_{n-1}) + (1-a)x_{n-1} $$ and I'm told that there is a solution of the form $c_1 + c_{2}\lambda^n$. How do I solve it, i.e. how ...
-2
votes
0answers
23 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
34 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
25 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
60 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
39 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 [closed]

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
39 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
36 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