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

learn more… | top users | synonyms (2)

3
votes
2answers
49 views

Solution to recurrence relation: $f(x) = f(x-2)+f(x/2)$ for even $x$, $f(x)=f(x-1)$ for odd $x$.

I need to find a solution for, or at least a way to compute efficiently, the following recurrence equation: $$f(x) = \begin{cases} f(x-2)+f(x/2), & \text{if $x$ is even} \\ f(x-1), & ...
1
vote
2answers
31 views

Linear Recurrence - Form not familiar

To start off, I am not looking for the answers to this question, only a how-to. I would like to figure out the solutions myself, but I don't know where to start with this one. The form described was ...
0
votes
0answers
20 views

Recursive formula for mathematical expression

Assume that $\alpha , n,\lambda \in \mathbb{N}$,and $f$,$g$ two real valued functions defined on $\mathbb{N}$. Function $W$ is given by the following formula. \begin{equation} W(n) = \max_{1 \leq ...
0
votes
1answer
20 views

Recurrence for the number of n tuples with restrictions

If $a_{n}$ is the number of $n$ tuples $(b_{1}, b_{2},...b_{n})$ with $b_{i} \in[4]$ that have at least one 1 and have no 2 appearing before the first 1. What is the recurrence for $a_{n}$?
0
votes
1answer
15 views

Finite Difference Equation with Constant Co-efficient

I trying to find tutorials on the topic (Finite Difference Equation with Constant Co-efficient) but I can't get exactly what I want. The said Difference Equation has a ...
2
votes
4answers
71 views

How to form a recurrence for a $n$-digit sequence using digits $0,1,2,3$ so that we have even no of $0$'s?

If we assume $T(n)$ to be the function representing the case where we have even number of $0$'s then $T(1)=3$ precisely strings $1, 2$ and $3$. $T(2)= 10$ ($00,11,22,33,12,21,13,31,23,32$). Likewise I ...
1
vote
0answers
24 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
1answer
49 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} ...
0
votes
1answer
22 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
11 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 ...
-1
votes
2answers
56 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}$.
1
vote
2answers
83 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 ...
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
75 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 ...
-3
votes
1answer
44 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 ...
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 ...
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
19 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
11 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
55 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
56 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
19 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 ...
0
votes
1answer
48 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) ...
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 ...
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
0answers
26 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.
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 ...
2
votes
2answers
50 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.
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 < ...
0
votes
1answer
28 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 ...
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
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 ...
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}$. ...
2
votes
5answers
82 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 ...
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
25 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
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 ...
-1
votes
1answer
63 views

find number of strings

Find the number of strings consisting of only a and b which have P occurrence of aa Q ...