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

learn more… | top users | synonyms (2)

0
votes
0answers
49 views

consider the function $f(1) = 1$, $f(n) = \sum_{i = 1}^{n - 1}(if(i))$ for $n > 1$

Consider the function $f(1) = 1$ $f(n) = \sum_{i = 1}^{n - 1}(if(i))$ for $n > 1$ Let $A(n)$ be the worst-case number of scalar arithmetic operations (+,-,*,/) required by this function for ...
0
votes
1answer
51 views

Convert recursive formula to explicit formula using backtracking

This is a question from the book Discrete Mathematical Structures by Bernard Kolman, Robert C. Busby and Sharon Cutler Ross. I want to find the explicit formula of the following recursive formula ...
4
votes
2answers
72 views

Ramanujan's infinitely nested radical clarification

I was reading Wikipedia's article for nested radicals (link here), when I stumbled across Ramanujan's problem. I was following along fine until it got to the step where $F(x+n)$ had to be simplified. ...
35
votes
0answers
618 views

Mirror algorithm for computing $\pi$ and $e$ - does it hint on some connection between them?

Benoit Cloitre offered two 'mirror sequences', which allow to compute $\pi$ and $e$ in similar ways: $$u_{n+2}=u_{n+1}+\frac{u_n}{n}$$ $$v_{n+2}=\frac{v_{n+1}}{n}+v_{n}$$ $$u_1=v_1=0$$ ...
1
vote
2answers
49 views

Generating function to find the number of ways to put marbles in a basket

Write a generating function for the number of ways to make a basket of $n$ marbles, if you need to use at least one orange marble , an even number of yellow marbles, at most 2 green marbles, and any ...
0
votes
0answers
17 views

Inhomogeneous Legendre recurrence relation

How can I find the particular solution to following recurrence relation for $F_n(x,r)$?: $$nF_n +(2n-1)xrF_{n-1}+(n-1)r^2F_{n-2}=1$$ Withe initial values $F_0=0, F_1=1$. The corresponding ...
0
votes
6answers
91 views

Prove that the sequence: $a_1 = 1, a_{n+1} =\sqrt{c+da_n}$ (when the real numbers $c, d > 1$) is converging and find it's limit

I have a summarized solution but it's starts with proving that the sequence is bounded from above by c+d. How can I know that this sequence is bounded by c+d? I understand the proof by induction but ...
1
vote
2answers
56 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 ...
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
431 views

$ \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
263 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 ...
3
votes
2answers
62 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), & ...
2
votes
1answer
63 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
19 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
85 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
33 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
74 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
101 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
79 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
53 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
27 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
71 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
28 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
50 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
28 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
31 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
200 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
56 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 ...
3
votes
2answers
59 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?