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

learn more… | top users | synonyms (2)

3
votes
2answers
37 views

Problem to understand a recurrence relation

In Norris, Markov chains, I found the following: [...] a recurrence relation of the form $$ ax_{n+1}+bx_n+cx_{n-1}=0 $$ where $a$ and $c$ were both non-zero. Let us try a solution of ...
1
vote
0answers
44 views

Difference equation of second order system with zero

I saw from lecture notes that difference equation of a first order system is like this: (1) (2) (3) (4) 1. What happens between (3) and (4)? It looks like inverse Z-transform but according ...
4
votes
3answers
260 views

What is the most elementary way of proving a sequence is free of non-trivial squares?

Given the sequence A001921 $$ 0, 7, 104, 1455, 20272, 282359, 3932760, 54776287, 762935264, 10626317415, 148005508552, 2061450802319, 28712305723920, 399910829332567, \dots $$ which obeys the ...
5
votes
3answers
67 views

Divergence of $a_{n+1}=\sqrt{2a_n+3}$?

I am wondering what I am missing from my proof. I would like to show that the limit of the sequence $$a_{n+1}=\sqrt{2a_n+3},\,\, a_1=4,$$ goes to $\infty$, as $n \rightarrow \infty$. Is there ...
2
votes
1answer
63 views

How do you prove uniqueness of solution of homogeneous linear recurrences?

I was following the MIT 6.042 course on OCW (that don't cover generating function on the lectures, sorry if the answer is easier by doing that method). Recall a linear homogeneous recurrences is of ...
0
votes
1answer
58 views

how to calculate a modified fibonacci via matrix exponentiation

If I modify the fibonacci recurrence to be the following way: f(0) = 1 f(1) = 1 f(N) = f(N - 1) + f(N - 2) + 1 Is it possible to represent this recurrence in a matrix equation similar to the one ...
1
vote
0answers
14 views

What method to use to find a hypothesis of the solution of the recurrence relation?

Suppose that we want to find an asymptotic upper bound for a recurrence relation: $T(n)=aT \left ( \frac{n}{b}\right)+f(n)$ , $T(n)=c, \text{ when } n \leq n_0$, using the following method: We choose ...
1
vote
1answer
28 views

Linear recurrence by characteristic equation.

Consider the linear recurrence $a_n = 2a_{n−1} − a_{n−2}$ with initial conditions $a_1 = 3, a_0 = 0$. We have $x^2 − 2x + 1 = (x − 1)^2$. Thus $ x = 1$ and $a_n$ = $u(1)^n + v(1)^n$. Why do we get ...
4
votes
1answer
37 views

Good (asymptotic) upper bound for recurrence over divisors

I am looking for a good (asymptotic) upper bound on the following recurrence relation ($T(0) = 1)$: $$ T(n) = \left[ \sum_{1\leq d<n, d|n} T(d) \right] + 1 $$ Note that the recursion is only for ...
1
vote
1answer
43 views

How do I solve for the recurrence relation when P does not exist?

I'm using the method that my textbook uses. I first put the recurrence relation in the form of a matrix. After that I solve for the eigenvalues and eigenspaces to find P. Then they use P to find D and ...
0
votes
3answers
44 views

Prove that $S_n = 5^n - 1$

Use Strong Induction: $s_0 = 0 $, $s_1 =4$ and $s_n= 6s_{n-1} - 5s_{n-2}$ for all $n\in \mathbb{N} \setminus \{1\}$ Prove that $S_n = 5^n - 1$ In regards to the first step, can I start at n=2? Not ...
1
vote
1answer
27 views

Difference Equation, verify expression is solution to the equation

I am reading a book on Probability, and do not know how to solve this example question. Consider the following difference equation and initial condition(s). In each case, verify that the expression ...
0
votes
0answers
14 views

help solve this recurrence realtion

1.T(n) = T(n^(1/3))+3 and 2.T(n) = 2T(n − 2) + 2 By using Master theorem. For the second one I guess the solution is θ$(2^n)$.
2
votes
0answers
24 views

Complexities of Recurrences in the form $t(n) = t(\alpha n) + t(\beta n) + cn$ [duplicate]

When considering recurrence relations, they are generally of a form similar to $$t(n) = t(\alpha n) + t(\beta n) + cn$$ and there are three cases to be considered for our values of $\alpha$ and ...
0
votes
2answers
40 views

Difference equation, special solution

I have the difference equation: $x_{n+2} - \frac{1}{2}x_{n+1} + \frac{1}{8}x_{n} = \cos(\frac{n\pi}{2})$ I am guessing the special solution is on the form: $A\cos(\frac{n\pi}{2}) + ...
2
votes
0answers
48 views

Validity of approximating a difference equation with a differential equation

Consider the following difference-differential equation defined for positive integer indices $k$ and $t$: $$ A_k(t+1)-A_k(t)=\beta \frac{ A_{k-1}(t)- A_k(t)}{\alpha+2 t} + \delta_{k \beta} . \tag{1} ...
0
votes
3answers
69 views

Prove that the sequence $a_{n+1}=\sqrt{2a_n+3},$ $a_1=1$, is bounded.

Prove that the sequence $a_{n+1}=\sqrt{2a_n+3},$ $a_1=1$, is bounded. Proof: it's increasing and bounded above by $2$. Is that right?
2
votes
5answers
127 views

How to give a good guess to the recurrence relation problem [duplicate]

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
40 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 ...
3
votes
4answers
74 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
33 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 ...
4
votes
1answer
74 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
39 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
49 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
28 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
1answer
40 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
38 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
39 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
32 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
37 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 ...
1
vote
0answers
31 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
46 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
13 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
34 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
1answer
62 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
50 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
32 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
30 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
72 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,\ \ ...
1
vote
2answers
44 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
57 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
68 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
64 views

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

I am trying to solve the recurrence $T(n) = 3T(n/2)+n$ where $T(1) = 1$ and show its time complexity. $n$ can be assumed to be a power of $2$. So basically, I drew out the tree and found that: ...
1
vote
1answer
36 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
96 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
41 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
16 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) \; ...
0
votes
0answers
27 views

Verifying solution of difference equation?

I have the following difference equation - $2h_{x+1} - 5h + 2h_{x-1} = 0$ for $x = 1, 2, ...., 19$ The boundary conditions are $h_0 = 1$ and $h_{20} = 0$ How would I go about verifying that $h_x = ...
1
vote
1answer
28 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 ...
1
vote
1answer
66 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$ ...