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

learn more… | top users | synonyms (2)

1
vote
2answers
63 views

Recurrence involving derivative

I would like to get a closed form of $A_n(x)$ if verifies the following recurrence relation $$A_n(x)=\frac{d}{dx}\left(\frac{A_{n-1}(x)}{a-\cos x}\right)\,\,\,\text{and}\,\,\,A_0(x)=1.$$ Really I ...
1
vote
0answers
30 views

Non linear recurrence from a different problem here

Referring to Non linear recurrence relation? "The recurrence (2) then implies that $ h_m=h_0+md$ for (m≥0)", What does $h_0$ refer to and how is it derived? From what I can see in equation(2), when $...
1
vote
0answers
26 views

$T(n) = 2T(\frac n 2) +\frac n {\log n}$ and the master theorem

I tried to use the master theorem to solve $T(n) = 2T(\frac n 2) +\frac n {\log n}$, and I got $\frac n {\log n} \overset{?} = O(n^{1-\epsilon})$, now it looks like it should work: $\frac n {\log n} \...
0
votes
2answers
102 views

Initial conditions that converge to an unstable equilibrium

Consider the discrete-time dynamical system \begin{align} x_{k+1}=T(x_k), \end{align} where $k\in\mathbb{N}$, $x_k\in\mathbb{R}^n$, $x_0$ is the initial condition, and $T:\mathbb{R}^n\to\mathbb{R}^n$ ...
1
vote
2answers
32 views

Recurrence relation in series with parameter $k$

I was given a recurrence relation of this series: $$a_{n+1} = k -a_n$$ $S_n$ is the sum of $n$ first terms of the series. So I was given that $$S_{101} = 353$$ $$S_{199} = 696$$ With this information ...
0
votes
0answers
47 views

Function that generates a Grass Leaf (as a list of vectors (or vertices))

I've tried to implement procedural grass generation into my little Graphics Engine but got stuck at the following mathematical problem: Let $GrassLeaf:\mathbb{R}^2\times(0,\infty)\times(0,\infty)\...
5
votes
0answers
59 views

$0< a_{n+1} \le a_{n} < 2$ and $b_{n+2}=a_n b_{n+1} - b_{n}$ Prove $b_n$ is bounded [closed]

Assume $\{a_n\}$ and $\{b_n\}$ are two sequences and $a_1 < 2$. For every integer $n$, $0 < a_{n+1} \le a_{n}$ and $b_{n+2}=a_n b_{n+1} - b_{n}$. Prove that $b_n$ is bounded.
27
votes
2answers
459 views

Convergence of sequence: $ \sqrt{2} \sqrt{2 - \sqrt{2}} \sqrt{2 - \sqrt{2 - \sqrt{2}}} \sqrt{2 - \sqrt{2 - \sqrt{2-\sqrt{2}}}} \cdots $ =?

In other words, if we define a sequence $$ \displaystyle a_{n+1} = \sqrt{2-a_n}, \,\,\,a_0 = 0 .$$ Then, we need to find $$ \displaystyle \prod_{n=1}^{\infty}{a_n}. $$ Well, from here I don't seem ...
0
votes
2answers
16 views

Finding a solution for a recurrence relation when you have a lone constant in the relation

Problem: $a_n = a_{n-1} - 3, a_0 = -1$ I can't find anything on how to solve for the solution formula when you have a constant in the recurrence relation (in this case the -3). Can someone give me a ...
0
votes
3answers
42 views

Using generating functions to solve a recurrent relation

I have one question on my Discrete Math homework that involves using generating functions, and I'm at a complete loss for how they work. The question asks: "Use the generating function method to ...
8
votes
1answer
269 views

How to solve $ \sqrt{x^2 +\sqrt{4x^2 +\sqrt{16x^2+ \sqrt{64x^2+\dotsb} } } } =5\,$?

How to find $x$ in: $$ \sqrt{x^2 +\sqrt{4x^2 +\sqrt{16x^2+ \sqrt{64x^2+\dotsb} } } } =5 $$
1
vote
0answers
17 views

Find finite-history recurrence from full-history recurrence?

In this question I asked for a closed-form solution to this functional differential equation: \begin{align*} f'(z) &= e^{-2} (f(z/e))^2 \\ f(0) &= 1. \end{align*} It doesn't look like there ...
0
votes
0answers
15 views

On an asymptotic recurrence

Fix $c\in\Bbb R$. Denote $A_0=M_0=n$. Consider $A_{i+1}=A_i+\lceil A_i^c\rceil$ and $M_{i+1}=M_i\times \lceil M_i^c\rceil$. How fast does $A_i$ grow for different ranges of $c$? $M_i$ grows as $n^{...
3
votes
2answers
64 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), & \text{...
2
votes
1answer
67 views

probability of not getting same number twice in a row after n die rolls

Having rolled a die $n$ times, I want to determine the probability of not getting any number twice in a row. If I wanted the probability of not getting any number three times in a row, I could use the ...
1
vote
2answers
40 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
23 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
23 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
21 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
87 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
34 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
67 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
25 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 ...
-1
votes
2answers
75 views

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

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
104 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
22 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
80 views

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

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
46 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
58 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
29 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
29 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
17 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 ...
2
votes
2answers
73 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
62 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
30 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 $P_{...
0
votes
1answer
51 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
29 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
32 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 ...
4
votes
7answers
202 views

Convergence of $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
58 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
40 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
30 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 $a_{n+...
3
votes
2answers
60 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
23 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
22 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
25 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
21 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 < 1$. ...
0
votes
1answer
55 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
30 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)$ ...