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

learn more… | top users | synonyms (2)

1
vote
0answers
17 views

Difference Equations and Discrete Integral and Derivative

So I'm trying to learn difference equations, and the book that I'm using defines the following: The discrete derivative of a function $a_n$ of the integers is defined as: $$ D a_n = a_{n+1} - a_n $$ ...
0
votes
0answers
26 views

Finding closed form expression for a multiple sum.

Let $n_1$, $n_2$ and $m$ be non-negative integers and let $\theta_1$ and $\theta_2$ be real numbers subject to $\frac{\theta_1}{\theta_2} = 1+m$. We consider a following multiple sum: \begin{eqnarray} ...
1
vote
2answers
78 views

Find the recursive definition for the number of strings on 0, 1, 2 avoiding the substring 012?

This is the question $a(n)$ the number of strings on $0, 1, 2$ avoiding the substring $012$ and the answer is $$a(n)=3a(n−1)−a(n−3)$$ with $$a(0)=1,a(1)=3,a(2)=9$$ My question is how to you get this ...
-1
votes
2answers
48 views

Number of words of length $n$ on the alphabet $a,b,c$ recurrence. [on hold]

Let $a_{n}$ be the number of words of length $n$ on the alphabet $a,b,c$ such that $b,c$ are not adjacent. What is the recurrence relation for $a_{n}$.
0
votes
1answer
15 views

Find the asymptotic solution $\Theta$ of the recurrence using the master theorem

I just took a quiz for an algorithms class that I didn't do so well on. It was on the master theorem. Unfortunately the professor refuses to supply answers or even tell me what I got wrong, so I was ...
0
votes
0answers
10 views

Understanding the three cases of the master theorem

I have been trying to understand how to use the Master Theorem to solve recurrence relations. I understand how to set up the variables and when to use the Master Theorem, but I do not understand what ...
-3
votes
1answer
41 views

Find a formula for this

I need help. I don't know if it is possible. Example formula that uses English instead of math! $f(x) = 3x$ + all previous values of $f(i)$ with $i$ from $0$ to $x-1$, where $x$ is a positive ...
0
votes
0answers
18 views

Non-linear simultaneous recurrence system

Given a non-linear, non homogeneous, discrete time recurrence system: $a_i^t = f_i(a_1^{(t-1)},a_2^{(t-1)},\ldots,a_k^{(t-1)},C_1)$, for all $i\in [k]$ where $C_1,\ldots,C_k$ are constants and each ...
1
vote
1answer
74 views

Recurrence relation $a_{n+1}a_{n-1} = 1 + a_n$ [on hold]

Consider the recurrence relation: $a_{n+1}a_{n-1} = 1 + a_n$ with initial values $a_1=x$ and $a_2=y$. Is this an example of a homogeneous equation or just a linear one? In any case does anyone have ...
2
votes
1answer
43 views

Master method and choosing $\epsilon$

I am reading CLRS3, currently Chapter 4 and Section 4.5, "The master method for solving recurrences." I understood what is the $\epsilon$ , but I can't understand why they choose $ \epsilon ...
1
vote
2answers
72 views

Recurrence Relations with ternary strings

Find and solve a recurrence equation for the number gn of ternary strings of length n that do not contain 102 as a substring. I am having some trouble finding the recurrence relation for this ...
0
votes
1answer
24 views

Solve the recurrence using the Master Theorem: $T(n) = 5T\left(\frac{n}{4}\right) + n\lg \lg n$

I am trying to solve the recurrence: $$ T(n) = 5T\left(\frac{n}{4}\right) + n\lg \lg n. $$ I tried to apply the Master Theorem but it didn't get me anywhere: $$ a=5,\; b=4\; \text{ and } f(n) = n\lg ...
0
votes
0answers
17 views

Proof by Induction for Recurrence Relations

I've been trying to work through this proof as an example problem in some lecture material and I want to confirm that my thought process is correct. Here is the problem: $\ T(n) = 2T(n/2)+2n, T(1) = ...
0
votes
0answers
19 views

Solve the recurrence $T(n) = 2T(n/2) + n/\log n$

Hi am trying to solve the recurrence $T(n) = 2T(n/2) + n/\log n$. It almost matches the master theorem except for the $n/\log n$ part?
0
votes
0answers
24 views

Solve recurrences using masters theorem

So the situation is that I need to solve the following recurrence. $T(n) = 8T(n/3) + 3n^2 \lg^3(n)$ I know that during master's theorom (or at least the way my professor is teaching) A= 8, B= 3 and ...
0
votes
0answers
16 views

A non-linear difference equation

I wanna anyone can help me with the following difference equation: $$(x_{n+2}-x_{n+1})-(x_{n+1}-x_n)=\left(x_n+\frac{1}{c}\right)(x_{n+2}-x_n)$$ where $c$ is a constant. I wanna know if there exists ...
0
votes
0answers
10 views

What are disadvantages of solving difference equations backwards?

Say you have the initial value of 100th and 99th term and you want to see how much error is in 1st term instead of picking values from the table for 1st and 2nd term and propagating to 99th and 100th ...
-1
votes
0answers
20 views

Solution to recursive equation

what will be the form of solution for this kind of recurrence equation? $$P_{n+1} + \dfrac{2n P_n}{x} - P_{n-1} = 0$$ $x$ is a constant. Will a guess solution of form $\lambda^n$ work? I need to ...
2
votes
2answers
52 views

Comparing a Factorial and a Perfect Power

Let us define the following recurrence relations as so. $$a_1=6, a_{n+1}=a_n!$$ $$b_1=6, b_{n+1}=6^{b_n}$$ So, which of the following is larger? $a_{b_2}$ or $b_{a_2}$? To clarify, I am trying to ...
2
votes
2answers
55 views

I am having trouble solving $T(n) = T(n/2) + n^2$

I am working with the equation $T(n) = T(n/2) + n^2$, given $T(1) = 0$. I started by using backwards substitution arriving at $T( ( ( n - 1 ) / 2 ) + ( n - 1 ) ^ 2 ) + n ^ 2$ and eventually arrived ...
0
votes
1answer
18 views

Using Rodrigues' formula to show a result

use the formula $P_n(x) = \dfrac{1}{2^nn!}\dfrac{d^n}{dx^n}((x^2-1)^n)$ to show that $P_{2n}(0) = \dfrac{(-1)^n(2n)!}{4^n(n!)^2}$ and odd terms are 0. I first subbed in 2n to the formula and got ...
1
vote
0answers
29 views

In a recurrence relation, how do we know which order to terminate?

By employing Frobinious or Power Series approach, we my come up with a recurrence relation that is only solvable if we set any constant lower than $a_0$ or higher than $a_n$ vanish. For example, in ...
0
votes
1answer
47 views

Solving a $2$ variable recurrence

I have a recurrence relation defined as : $A(i, j) = A(i, j-1) + A(i+1, j)$ where both $i$ and $j$ are less than a fixed variable $N$. Also, $A(i,1) = 1\:\:$ for all $1 \leq i \leq N$. $A(N, j) ...
5
votes
7answers
151 views

Convergence of the recursive sequence $a_{n+1}=\sqrt{2-a_n}$

I'm attempting to prove the convergence (or divergence, though I strongly suspect it converges) of a sequence defined as $a_{n+1}=\sqrt{2-a_n}$ with $a_1=\sqrt{2}$. I cannot use the monotonic ...
0
votes
0answers
27 views

Prove equivalence between two Bessel functions relations

Given the following equation $$\frac{J_{n - 1} (u)}{uJ_n (u)} - \frac{K_{n-1}(w)}{wK_n(w)} = 0$$ (where $J$ is the Bessel function of the first kind, $K$ is the modified Bessel function of the ...
0
votes
0answers
25 views

Solve the Recurrence Relation to Get a Theta Bound

If I have $T(n)=T(n-5)+n$, how would I go about using induction to find a $\Theta$ bound for this. I was able to use a tree method to get that the bounds should be about $\frac{n^2}{5}$, but I am ...
0
votes
0answers
9 views

Practical example of non-homogenous recurrence relation

Could anyone provide a practical example of a non-homogenous recurrence relation from daily life? Sorry for asking such a trivial question.
2
votes
2answers
49 views

Solving the recurrence $A_n = \sum_{k=1}^{n} 2^{k+1} A_{n-k}$

Let me ask a very simple question: Let $(A_n)$ be a sequence of integers defined by $A_0 = 1$ and $$\forall n \geq 1 : A_n = \sum_{k=1}^{n} 2^{k+1} \cdot A_{n-k}.$$ There is an explicit formula for ...
1
vote
2answers
37 views

Solve a linear system of equation involving some recursion

$$ \begin{align*} x_{1} &= 1 + x_{2}\\ x_{2} &= 1 + \frac{1}{2} x_{3} + \frac{1}{2} x_{1}\\ &\vdots\\ x_{i} &= 1 + \frac{1}{2} x_{i+1} + \frac{1}{2} x_{1}\\ &\vdots\\ x_{n-2} ...
1
vote
0answers
27 views

Solve this recurrence relation via a first order partial differential equation?

Find a general formula for $a_{n,k}$ , for $n,k\geq1$. We have initial values $a_{1,1}=1$, and $a_{1,k}=0$ for $k>1$. The recurrence relation is: $a_{n+1,1}=-a_{n,1}$ , for $n\geq1$ and ...
3
votes
2answers
53 views

If $\lim_{n \rightarrow \infty} a_n=L$ then $\lim_{n \rightarrow \infty} f(a_n)=f(L)$?

If we have for example $a_n=1+\sqrt{a_{n-1}}$ and $\lim_{n \rightarrow \infty} a_n=L$ then can I say that $ L=1+\sqrt{L}$? If it's so, what's the proof?
0
votes
1answer
19 views

Recurrence solving

Suppose recurrence is $a_{n+2}=a_{n+1}+6a_{n}$ Tried to solve it with solving $Fnc(n)=An^5+Bn^4+Cn^3+Dn^2+En+F$ Which gives $A = (-33/4), B = (365/4), C = (-1385/4), D = (2155/4), E = (-551/2), F = ...
0
votes
0answers
20 views

Mistake in recurrence relation text book?

I'm sorry for posting this here, but I would like to confirm my doubt about the correctness of the systems of equation in the textbook example. I enclosed an image.
2
votes
5answers
79 views

Limit of the sequence defined by a recurrence

Given a recurrence formula for an arithmetic sequence, $$U_{n} = \frac{1}{2+U_{n-1}}$$ Show that$$\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2+ ...}}}} = (SomeGivenValue)$$ How can we solve questions ...
1
vote
1answer
18 views

How to solve this recurrence $t(n) = ( 2^n )( t(n/2) )^2$ with $t(1)=1$?

I have been wondering about how to solve this recurrence but I don't get to any feasible solution. How can I do it?
0
votes
0answers
16 views

Recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$,$\sum\limits_{i=1}^{k}c_i < 1$ is linear

Let $L: \mathbb N_0 \to \mathbb N_0$ satisfy the recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$ with $c_i \geq 0$ for $i=0,\ldots, k$ and $\sum\limits_{i=1}^{k}c_i < ...
3
votes
1answer
29 views

Rational Points on Fibonacci-like Sequence of Polynomials

Let $\{a_n\}$ be a sequence of polynomials in $\mathbb{Q}[x,y]$ with $a_0=0,a_1=1$, and $$a_n=xa_{n-1}+ya_{n-2}$$ The first few look like $$a_3:y+x^2$$ $$a_4:2xy+x^3=x(2y+x^2)$$ $$a_5:y^2+3x^2y+x^4$$ ...
0
votes
1answer
27 views

Non-homogenous recurrence relation. How to find the particular solution?

I have enclosed one image of two textbook pages. There is a system of equation (see frame) on page 2. I do not understand why both terms can be set equal to 0 (zero)to solve it. Thank you for the ...
0
votes
0answers
23 views

Master Theorem for common recurrence

I have the following recurrence: $$T(n) = T\bigg(\frac{n}{2}\bigg) + O(n)$$ And I am trying to find the time complexity using the master theorem. So I have: $a = 1, b = 2$ $f(n) = O(n) = c(n)$ ...
0
votes
1answer
34 views

Find the order of elimination in Josephus Problem

Josephus Problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game. People are standing in a circle waiting to be executed. Counting begins at the first ...
2
votes
5answers
113 views

Solution to the recurrence relation

I came across following recurrence relation: $T(1) = 1, $ $T(2) = 3,$ $T(n) = T(n-1) + (2n-2)$ for $n > 2$. And the solution to this recurrence relation is given as $$T(n)=n^2-n+1$$ However ...
0
votes
0answers
16 views

Big-Oh, Big-Omega, Big-Theta determination

I am given a recurrence relation and told to solve it. Once we solve it we are supposed to determine whether it is in $O(f(n)), \Omega(f(n))$, or $\Theta(f(n))$. The relation is $t_n = 2nt_{n-1}$. ...
5
votes
2answers
672 views

How to find recurrence relation of a given solution.

Determine values of the constants $A$ and $B$ such that $a_n=An+B$ is a solution of the recurrence relation $a_n=2a_{n-1}+n+5$. I know that the characteristic equation is $r-2 = 0$ which has the root ...
0
votes
1answer
17 views

Recurrence relations with multiplication

I have a recurrence relation and I am not quite sure if I am solving it correctly. The relation is this: $t_n = 2nt_{n-1}$ where $t_0 = 1$ Here is how I went about solving this: First step is to ...
1
vote
1answer
24 views

Recursive formula for word problem.

I'm having problems with this recursion problem: Ann wants to buy along several weeks one dressing item which can be of two kinds: small ones -- hats and scarfs, and big ones -- dresses, suits, gowns ...
0
votes
1answer
24 views

Can we solve this recurrence relation using recursion tree method

The recurrence relation is given as follows: $T(n) = 2T(\sqrt{n})+1$ $T(1) = 1$ I tried to solve it with recursion tree as follows: But to find the number of levels that may occur, I have to ...
1
vote
1answer
33 views

Non linear recurrence relation?

for $ f: \mathbb N \rightarrow \mathbb N $, How do I solve $ f_n - f_{n+2} = f_{n+3} \times (f_{n+2} - f_{n+4})$ I tried the generating function but it only seems to work for linear relations. any ...
0
votes
0answers
11 views

Solving a recurrence relation with 2 variables and 2 boundary conditions.

I am having some problem with solving a recurrence relation. Probably, the problem can be solved using a generating function, unfortunately I do not know how to deal with the boundaries of this ...
10
votes
3answers
254 views

Is the sequence defined by the recurrence $a_{n+2}=\frac{1}{a_{n+1}}+\frac{1}{a_n}$ convergent?

Let $a_0=1$, $a_1=1$ and $a_{n+2}=\frac1{a_{n+1}}+\frac1{a_n}$ for every natural number $n$. How can I prove that this sequence is convergent? I know that if it's convergent, it converges to ...
0
votes
0answers
29 views

Time complexity of $T(n) = 2^n + 2\sum_{i=1}^{n-2} T(i)$

$$ T(n) = 2^n + 2\sum_{i=1}^{n-2} T(i)$$ $$ T(0) = 1 , T(1) = 2 $$ This is my $T(n)$, and I need to find its time complexity. I know the answer is $T(n) = \theta (n2^n)$, but I have a problem with ...