Questions regarding functions defined recursively, such as the Fibonacci sequence.
2
votes
3answers
45 views
Solution to Recurrence Relation
I asked a question previously, about how to describe
$$
f(n) = n^3
$$
As a recurrence relation. I was, quite rightly, given $a_1=1$ and $a_{n+1}=a_n+3n^2+3n+1$.
I have attempted to solve it, using ...
2
votes
2answers
32 views
Expressing a sequence as a recurrence relation
I've been working on a project, and it's come to that time when I have to prove the run time complexity of an algorithm. I've obtained my metric and those things that have nothing to do with you guys! ...
0
votes
0answers
18 views
What are the asymptotic upper bounds to the recurrence $T(n) = 2T (⎣n/2⎦) + 2$ $n$ $lg$ $n, T(2) = 4$
The recurrence relation:
$T(n) = 2T (⎣n/2⎦) + 2$ $n$ $lg$ $n, T(2) = 4$
What are the asymptotic upper bounds close as possible to the recurrence above using the iteration method?
How to check if ...
1
vote
2answers
27 views
Recursive formulae involving a linear operator
Given a basis $e_{1}$, $e_{2}$ in the plane, define the linear operator $F$ as $F(e_{1})=3e_{1}+e_{2}$ and $F(e_{2})=e_{2}$. Furthermore, define the sequence $u_{1},u_{2},\dots$ of vectors in the ...
0
votes
1answer
37 views
Solve the recurrence $T(n) = T(\log_2 n) + 13n$
I have the following recurrence relation $$T(n) = T(\log_2 n) + 13n.$$
I believe in order to solve the equation I need to determine the height of the tree.
$$T(n) \to T(\log_2 n) \to ...
0
votes
0answers
29 views
Solving a Non-Homogeneous Divide and Conquer Recurrence with Characteristic Equation
I have this recurrence relation problem at hand, which I have to solve via a characteristic equation:
$$T(n)=2T({n/2})+4^n$$
To get rid of the $n/2$, I make the following change of variable $$n = ...
6
votes
1answer
40 views
Another recurrence… $T(n)=\sqrt{2n} \cdot T(\sqrt{2n}) + \sqrt{n}$
I'm trying to solve the following recurrence :
$$T(n)=\sqrt{2n}\cdot T(\sqrt{2n}) + \sqrt{n}$$
I've tried substituting $n$ for some other variables to transform the above to something easier without ...
5
votes
1answer
30 views
Recurrence $u_{n+1}u_{n-1}-u_n^2=Ar^{n-1}$
I was going through some old puzzles and encountered one where there was a non-linear recurrence of form $$u_{n+1}u_{n-1}-u_n^2=Ar^{n-1}$$ with $u_0$ and $u_1$ given.
I know I can use a test form ...
1
vote
2answers
68 views
Why do we substitute $\alpha^n$ in the recurrences of the form $ax_n=bx_{n-1}+cx_{n-2}$?
I encountered the following recurrence relation $2x_n-3x_{n-1}+x_{n-2}=0$ with $x_0=1$ $x_1=1$.I did not have any idea how to go about this.However, google pointed me to page 18 of Herbert Wilf's ...
1
vote
1answer
145 views
An issue with approximations of a recurrence sequence
By trying to give an approximation to a given recurrence sequence I encountered a problem.
To be more precise I have a method but it fails if the right condition is not met and I wonder how I should ...
16
votes
5answers
373 views
limit of : $a_{n+2} =\frac{1}{a_n} + \frac{1}{a_{n+1}}$
$a_n$ is a real sequence, $a_1,a_2$ are positive and for all $n>2$ : $$ a_{n+2} =\frac{1}{a_{n+1}} + \frac{1}{a_{n}}.$$
Prove that: $\displaystyle \lim_{n\to \infty} a_n$ exists, then find it.
...
0
votes
1answer
53 views
How to express this recurrence relation as a closed form?
I need a little help with expressing this recurrence relation as a closed form. I've already expanded it out to see the pattern:
$$
f(n) = f\left(\frac{n}{3}\right) + f\left(\frac{2n}{3}\right) + n - ...
0
votes
1answer
15 views
$A_k\leq C [2^{2k}A_{k-1}]^{\mu+1}, \ k=0,1,…$ implies $A_k\to 0$?
Consider the nonlinear recursive relation $$A_k\leq C [2^{2k}A_{k-1}]^{\mu+1}, \ k=0,1,...$$
where $C,A_k,\mu>0$. How can one show that if $A_0$ is small, then $A_k\to 0$?
Thanks.
0
votes
2answers
37 views
Equation of a curve whose difference in ordinate values form an arithmetic sequence
I have the following recurrence equation that I have obtained while trying to solve a problem:-
$$T(0) = 1$$
$$T(n) = T(n-1) + 9n - 8: n \ge 1$$
The values of $T(n)$ for $n = 0,1,2,... $ are as ...
2
votes
3answers
82 views
Solving recurrence equation using exponential generating functions
The recurrence is
$ a_n = (n-1) a_{n-1} + (n-2)a_{n-2} $
I tried using exponential generating functions and have problems with it (the second term mostly)
Further can this be solved without ...
1
vote
3answers
54 views
How to solve linear recurrences consisting of both $x_n$ and $y_n$?
I know how to solve a general linear, homogenous recurrence but these are the ones I've been given:(i) $x_{n+1} = 3x_n + 6y_n$(ii) $y_{n+1} = 6x_n - 2y_n$
Initial conditions: $x_0 = -1, y_0 = 0$
How ...
4
votes
1answer
122 views
Finding the general formula $a_n$ for $a_n = \frac{1}{2a_{n-1}} + 2a_{n-2}$
How to calculate the general formula $a_n$ for the following sequence:
$$a_n = \frac{1}{2a_{n-1}} + 2a_{n-2}$$
where $a_1=\frac{1}{2}, a_2=\frac{1}{4}$
0
votes
1answer
32 views
Recurrence equation with upper and lower boundary condition
A very natural set up for recurrence equations is the following:
$$ s(0) = 0 $$
$$ s(k) = A \ s(k-1) + B $$
$$ s(M) = A \ s(M-1), $$
where $0 \le A,B \le 1$ and $0 < k < M$.
We can omit the ...
1
vote
1answer
53 views
Generalized Josephus problem
I have been reading generalized Josephus problem from Concrete Mathematics. The recurrence form for the problem is given as
f(1) = a
f(2n) = 2f(n) + b, for n >= 1
f(2n+1) = 2f(n) + y, for n >= 1
...
1
vote
3answers
86 views
Strings and Substrings
So here is one of the last homeworks we are doing in my Discrete math class. It seems like it should be simple but I am really stuck. Any help would be greatly appreciated.
Find the ordinary ...
1
vote
1answer
40 views
Convergence of $x_n=\sqrt{2(x_{n-1}-\log(1+x_{n-1}))}$
$x_n=\sqrt{2(x_{n-1}-\log(1+x_{n-1}))}$ with $x_0=a\ge0$
I calculated some values for $x_n$ with $a=0,1,2$ and recognized its monotonically decreasing (It converges to $0$). Now the standard approach ...
0
votes
1answer
13 views
Upper Bounds of Two Interdependant Recursive Sequences
For a pair of real numbers $\alpha$ and $\beta$, I need to prove that for the sequences
$a_n = (-\alpha)a_{n-1} +b_{n-1}$
$b_n = (-\beta)a_{n-1}$
an upper bound exists with a form similar ...
0
votes
1answer
20 views
Master Method and use cases
$T(n)=T(n-2)+n^{2}$ and $T(n)=4T(n-2)+n^{2}$
Master method to solve these two equations? I know I can use the other cases where $a$ and $b > 0$ but since $T(n-2)$ do I assume $b$ is $1$?
0
votes
1answer
34 views
Rules Regarding Particular Solutions for Recurrence Relations
Suppose I have the recurrence relation
$a_n = - a_{n-1} + a_{n-2} + 2^n + n$
Is it alright to solve for the homogeneous 'general' solution and then split the solving of the particular solution into ...
3
votes
1answer
84 views
why must orthogonal polynomials each have distinct roots?
Let $\langle\cdot,\cdot\rangle$ be any inner product on the set of functions $[a,b]\rightarrow\mathbb{R}$, and let $(p_n)_{n\in\mathbb{N}}$ be a sequence of polynomials defined by:
$p_{-1}(x)=0$, ...
2
votes
5answers
102 views
Deriving Closed Form for a Recursion via Generating Functions
Consider (1) $a_{n+2} = 2a_{n+1} - a_n + 4n3^n$ with $a_0 = a_1 = 1$.
Using generating functions and setting $A(x) = \sum a_nx^n$ we obtain
$$\begin{align*}&\quad\sum a_{n+2}x^{n+2} = ...
2
votes
1answer
25 views
Finding the coefficient in the closed form of the generating function
I try to solve the recursion $a_n=5a_{n-1}+5^n$ with $a_0=1$ with generating function, but I could not find the coefficient of $x^n$ in the closed form
\begin{eqnarray*}
...
0
votes
1answer
43 views
Proof Involving Difference Operators
Let E be the forward shift operator on $x$ defined by $Ef(x) = f(x+1)$. Similarly, let $\delta$ be the forward difference operator such that $\delta f(x) = f(x+1) - f(x)$ and the inverse operator ...
2
votes
2answers
38 views
Using Generating Functions (again) to Solve Recurrences
Consider the recursion $a_n = 2a_{n-1} + (-1)^n$ where $a_0 = 2$
Then $A(x) = \sum a_n x^n$ = $2 + \sum a_n x^n$ shifting the index of summation. The only next move I can think of is to now ...
1
vote
1answer
36 views
Solving the recurrence $T(n) = T(n/2) + cn \cdot \lg \lg n - 1$
I'm trying to solve the recurrence
$$
\begin{eqnarray}
T(n) & = & T\left( \frac{n}{2} \right) + cn\lg \lg n - 1\\
T(2) & = & 0
\end{eqnarray}
$$
where $\lg n = \log_2 n$ to get the ...
4
votes
3answers
104 views
Combinatorial Proof for a Recursive Sequence
For $n>3$ let $g_n = g_{n-1} + g_{n-3}$ where the recursion takes the value 1 for n = 0,1,2.
Prove that $g_{2n} = (g_n)^2 + 2g_{n-2}g_{n-1}$ combinatorially, $n > 1$.
For the time being I am ...
2
votes
2answers
88 views
Tricks to Solve Arbitrary Recursions
Consider two recursions:
(1) $a_{n+2} = 2a_{n+1} - a_n + 4n3^n$ with $a_0 = a_1 = 1$
(2) $na_n = (n-2)a_{n-1} + n/2$ with $a_0 = 0$
When I look at the first recursion it suggests to me that I ...
1
vote
2answers
49 views
How to think about solving recurrences?
I am having trouble finding a closed-form solution to the following recurrence for $T(i)$, $0\le i\le n$.
$$T(0) = T(1) + 2,\quad T(n) = 0$$
and
$$T(i) = {T(i+1)\over 2} + {T(i-1)\over 2} + 1,\quad ...
4
votes
1answer
181 views
Lower bound for multivariate recurrence
I have a recurrence that looks like
$$p(i,j,k) = \frac{j}{n}p(i-1,j-1,k-1) + \frac{i-j}{n}p(i-1,j,k-1)$$
$$p(i,0,k) = 1$$
$$p(i,j,0) = 0$$
$$p(0,j,k) = 0$$
The base cases are to be considered in ...
0
votes
1answer
59 views
Solving a recurrence realtion using backward substitution.
So I've been trying my best to do this, and I have made some good progress, I just need to know if what I have done is correct and if not, what the hell am I doing wrong? :P
I start off with this ...
0
votes
1answer
30 views
Recurrence into explicit formulas
Can anyone point me in the right directions for these recurrence problems? I'm having trouble figuring this out for my class
I have to find the explicit formula for $H(n)$ as a fuction of $n$. ...
0
votes
1answer
87 views
Solving Recurrence Relation with Forward Substitution
I've found myself quite stuck on this recurrence relation. I've been given it to solve, via forward substitution and verify using induction. I start out with
$$
T(n) = 4T(n/3)
$$
For all $n > 1$ ...
0
votes
3answers
28 views
Recurrence relation of two next terms
For the recurrence relation, $a_{n+2}=3a_{n+1}-2a_n$ with $a_0=2$ and $a_1=3$, compute the first six terms of the sequence and derive a closed form formula for this sequence.
So I'm totally lost with ...
3
votes
1answer
41 views
Finding a Linear Recurrence Relation
A model for the number of lobsters caught per year is
based on the assumption that the number of lobsters
caught in a year is the average of the number caught in
the two previous years.
...
2
votes
2answers
46 views
Recurrence Relations for $c_1$ and $c_2$
For the following recurrence relation: $a_n = 3a_{n-1}+4a_{n-2}$, where $a_0=3$ and $a_1=2$ I solved it using quadratic equation by $x^2+3x-4$. So I got to $a_n = 4^nc_1 + c_2(-1)^n$. Now to find ...
2
votes
3answers
87 views
Solving functional equation for generating function
Find the functional equation for the generating function whose coefficients satisfy $$
a_n = \sum_{i=1}^{n-1}2^ia_{n-i}, \text{ for } n\ge 2, a_0 = a_1 = 1
$$
This is what I've tried so far:
$$
...
2
votes
3answers
51 views
How do I find the closed form of a recurrence relation?
I'm stuck on how to find closed forms of recurrence relations. My current problem is:
An employee joins a company in 1999 with a starting salary of $50,000. Every year this employee receives a raise ...
2
votes
2answers
66 views
Finding the expression for $q_n$
Let $q_n$ be the number of $n$-letter words consisting of letters a, b, c and d, and which contain an odd number of letters $b$. Prove that
$$q_{n+1} = 2q_n + 4^n\qquad\forall n \geq 1 $$
and, ...
1
vote
2answers
33 views
Stuck on solving recurrence relation
I'm trying to find formula for the following sequence.
1, 3, 6, 10, 15...
Recursive formula is pretty straightforward
My attempt to solve it:
Homogeneous solution
Particular solution
...
2
votes
1answer
45 views
Recurrence equation question
My question (which has been edited) relates to the following recurrence relation:
$$a_{j+2}=\frac{2 a_{j}}{j}$$
The book which I am reading says that the (approximate) solution is given by:
...
0
votes
3answers
44 views
Recurrence question
My question relates to the following recurrence relation:
$$a_{j+2}=\frac{a_{j}}{2}$$
The book which I am reading says that the (approximate) solution is given by:
$$a_{j}=\frac{C}{(j/2)!}$$
(I ...
0
votes
1answer
23 views
Recurrence Relations: general process for solving first order
So I had asked a question prior to this one about recurrence relations, but apparently it was a bad one to ask. So I'm trying again to understand how to solve these babies... Here it is:
$$
...
4
votes
1answer
39 views
Find the common limit of $\frac{2}{1/a_n+1/b_n}$ and $\sqrt{a_n b_n}$
Let $a_0=1$ and $b_0=2$, then
\begin{align}
a_{n+1} &= \frac{2}{\frac{1}{a_n}+\frac{1}{b_n}}, \\
b_{n+1} &= \sqrt{a_n b_n}.
\end{align}
The sequences $(a_n)$ and $(b_n)$ converge to the same ...
1
vote
3answers
53 views
Linear Recurrence Relations
I'm having trouble understanding the process of solving simple linear recurrence relation problems. The problem in the book is this:
$$
0=a_{n+1}-1.5a_n,\ n \ge 0
$$
What is the general process, and ...
2
votes
1answer
38 views
Finding functional equation for generating function
I'm given
$$
a_n = \sum_{i=2}^{n-2} a_ia_{n-i} \quad (n\geq 3), a_0 = a_1=a_2 = 1
$$
and I need to find the functional equation for the generating function satisfying the above equality. I obtained ...
