Tagged Questions

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

learn more… | top users | synonyms

0
votes
0answers
24 views

How to solve the following recurrence: $g(n) = g(\log{n}) + n^{1/2}$

It seems to me that the following recurrence: $g(n) = g(\log{n}) + n^{1/2}$ has a tight upper bound of: $O(n^{1/2})$, however I am not sure how to prove this. Specifically, I would like to find an ...
3
votes
2answers
29 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 ...
-3
votes
0answers
25 views

How to write recurrence relations from a verbal description(Question from Oxford math admission test)? [on hold]

Questions are interesting because they only require primary math skill. They have general patterns that developing the problem from specific to general. The 5th and 7th questions in the paper(linked) ...
3
votes
0answers
50 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
56 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
21 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
23 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 ...
0
votes
0answers
11 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 ...
4
votes
1answer
25 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
0answers
29 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
40 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 ...
0
votes
0answers
10 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)$.
1
vote
0answers
14 views

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

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 ...
2
votes
0answers
28 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{(k-1)A_{k-1}(t)-kA_k(t)}{\alpha+2\beta t} + \delta_{k \beta} . ...
0
votes
3answers
50 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
96 views

How to give a good guess to 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
30 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
34 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
24 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
60 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
34 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
18 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
20 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 [closed]

I am new to generating function.Can anyone please describe the process to find the generating function for given sequence? ...
2
votes
1answer
35 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
27 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
25 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
34 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
22 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
35 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
1answer
55 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
45 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
22 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
64 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
35 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
40 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
34 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
29 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
58 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
37 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 ...
1
vote
1answer
35 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
13 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} + ...