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

learn more… | top users | synonyms (2)

2
votes
1answer
32 views

Show $J_2(x) = (2/x)J_1(x)-J_0(x)$

The Bessel function of the first kind and order $p$ is given by: $$ J_{p}(x)= \sum_{n=0}^{\infty}\frac{(-1)^n}{n!\, \Gamma(n+p+1)}\left(\frac{x}{2}\right)^{2n+p} $$ I want to show that $J_2(x) = ...
-7
votes
2answers
142 views

Prove that this recurrence relation algorithm generates all positive rational numbers, and does so without repetition and in reduced form [closed]

For $n\ge 1$, generate a sequence $\{a_n\}$ such that for any even $n = 2k$: $$ a_n = a_k$$ And for any odd $n=2k+1$: $$ a_n = a_k + a_{k+1}$$ With initial conditions $a_1 = a_2 = 1$ Now, generate a ...
0
votes
1answer
61 views

Find a formula for the recurrence relation $x(n) = x(\lfloor n/2 \rfloor) + n\,a\,x(1) = 1$

Do you know how to find a formula for a sequence below? $$\begin{align*} x(n) &= x(\lfloor n/2 \rfloor) + n\\ x(1) &= 1 \end{align*}$$ What is $x(2^k)$? What is $x(n)$ when $2^k \leq n < ...
0
votes
1answer
33 views

Recurrence relation for a differential equation

I am reading a book that talks about series solutions of differential equations, and I couldn't seem to understand the following question: Consider the differential equation and use the ...
1
vote
1answer
21 views

Solve linear homogeneous recurrence relation?

The relation to solve is this: $$ a_{n} = 7a_{n-1} - 10a_{n-2}, a_{0} = 5, a_{1} = 16$$ So $$ a_{2} = 62, a_{3} = 274, ...$$ So I thought I was supposed to be able to do this to solve: $$ x^n = ...
1
vote
1answer
30 views

Price of a commodity converges to a limiting price

We let $Q_k$ denote the supply of commodity, $D_k$ the demand for the commodity, and $p_k$ the price at $k$-th time. The demand depends on the current price, $D_k=a+bp_k$ and the supply depends on ...
1
vote
6answers
47 views

Solving recurrence relations?

How do I solve $$ a_{n} = a_{n-1} + n, a_{0} = 1$$?? I solved for n=1 thru n=5: 1: 2 = a0 + 1 2: 4 = a0 + 1 + 2 = a0 + 3 3: 7 = a0 + 3 + 3 = a0 + 6 4: 11 = a0 + 6 + 4 = a0 + 10 5: 16 = a0 + 10 + 5 = ...
0
votes
1answer
21 views

How to solve linear homogenous recurrence relation w/ constant coefficient a{n} = -3a{n-1}, a{0} = 2 (and {} denoting subscript)?

I'm totally confused by recurrence relations. We just learned about relations, I don't even see the relation part... so solving them is not coming easily to me at all. In fact everything I see or read ...
1
vote
0answers
20 views

binomial coefficient and recurrence relation [duplicate]

any hints on how to solve the recurrence relations for the following binomial coefficient \begin{equation} {n \choose k}=\begin{cases} 1, & \text{if $k\in\{0,n\}$}.\\ {n-1 \choose ...
1
vote
1answer
43 views

Difference equation with log

Can we find continuous $f(x)$ and $d$ such that $$ f(x+1)-f(x) = -\log( c|x| + d ) $$ for all $x$? The constant $c>0$ is specified.
1
vote
1answer
25 views

Recurrence Relations: Understanding Homogeneous Reccurences

In an effort to better educate myself on the practices of Discrete Math. I have been attempting several practice problem sets. While most of the concepts up to this point have made sense, I find ...
0
votes
0answers
12 views

Prove Asymptotic Stabillity of two cycle

Given the quadratic function $Q(x)=ax^2+bx+x$ where $a\ne0$ and a two cycle {d,e} such that $Q'(d)*Q'(e)=-1$, prove that the two cycle is asymptotically stable.
0
votes
2answers
44 views

Recurrence relation using generating function

I tried to solve recurrence relation using generating functions \begin{align} T(k) &= 3 T(k-1)-3T(k-2)+T(k-3) \\ T(0) &= 1 T(1) = 3 T(2) = 6 \end{align} My approach was to equal ...
0
votes
0answers
8 views

QBF - space complexity in detail

As I'm new to the "complexity theory" stuff I've some trouble with proofs which are "obvious" regarding all books I've found so far. In this case I want some evidence why a certain algorithm has space ...
4
votes
0answers
32 views

Solving system of nonlinear difference equations

This is perhaps a trivial question (I’m an economist), but as a non-matematician that might elude me. I have a (two variable) system of nonlinear difference equations (similar to Riccati type ...
2
votes
1answer
33 views

How to prove that nth differences of a sequence of nth powers would be a sequence of n!

Given an infinite sequence of numbers, first differences denote a sequence of numbers that are pairwise differences, second differences denote a new sequence of pairwise differences of this sequence, ...
2
votes
3answers
26 views

Limit of a difference equation

Given $y_{k+1} = 1 + \sqrt{y_k}$ for $k \geq 0$ and $y_0 = 0$, we have a limit of the form $L = \lim_{k \rightarrow \infty} y_k = 1 + \sqrt{1 + \sqrt{1 + \sqrt{1 + ... \sqrt{1 + \sqrt{2}}}}}$. ...
0
votes
1answer
30 views

Second-Order Linear Homogeneous Recurrence Relations with Constant Coefficients

How would I find sequences that satisfy the following relation? $$a_{n+2} = -a_{n+1} + 5a_{n}$$ $$\text{given:}\quad a_{0} = 2, a_{1} = 8, \text{ and }(n \ge 0)$$
2
votes
0answers
23 views

Deriving a recurrence equation and apply Master's Thrm to it

So for a function such as: function Hi(n) if n > 1 then for j ← 1 to n do print(”Hi”) Hi(n/2) Hi(n/2) Hi(n/2) It's very easy to eyeball this and get a ...
6
votes
1answer
239 views

convoluted recurrence: $f(2n)=f(n)+f(n+1)+n, f(2n+1)=f(n)+f(n-1)+1$

For the recurrence relation: $f(0)=1$ $f(1)=1$ $f(2)=2$ $f(2n)=f(n)+f(n+1)+n\ \ \ (\forall n>1)$ $f(2n+1)=f(n)+f(n-1)+1\ \ \ (\forall n\ge 1)$ (the first numbers of the sequence are: 1, 1, 2, ...
1
vote
2answers
29 views

Explicit formula for recurrence relation

I am given recurrence relation : an = 5an/2 + 3n, for n = 2,4,8,16... and a2 = 1. I found first 4 terms and I don't see a pattern. a4 = 5*1 + 3*4 = 17 a8 = 5*17 + 3*8 = 109 a16 = 5*109 + 3*16 = 593 ...
1
vote
0answers
26 views

Calculate the total cost

According to my notes: $$T(n)=T\left(\frac{n}{2} \right)+T\left(\frac{n}{4} \right)+T\left(\frac{n}{8} \right)+n$$ Th recursion tree is this: Cost per level $i \to \left( \frac{7}{8} ...
1
vote
0answers
21 views

Recurrence with Polynomial Coefficients of $n$

How would I solve a recurrence relation like $$a_n = f_1(n)a_{n-1} + f_2(n)a_{n-2} + ... + f_k(n)a_{n-k} + g(n)$$ where $f_1, f_2, ..., f_k, g$ are polynomials and $\left \{a_n\right \}$ is my ...
0
votes
1answer
90 views

Using the contraction principle to prove that the sequence $a_n=f(a_{n-1})$ is convergent where $f(x)=1+1/x$

Define function $f(x)$ from $\mathbb R^1$ to $\mathbb R^1$ by $f(x) = 1+1/x$. Define $a_n$ inductively by $a_1=1$ and $a_n=f(a_{n-1})$ for $n \geq 2$. Prove using the contraction principle that ...
0
votes
1answer
28 views

Stability of equilibrium points

Given the difference equation and the continuously differentiable function $g$: $$x(n+1)=x(n)+h\times g(x(n))$$ Determine conditions on $h$ for which an equilibrium point is asymptotically stable, ...
0
votes
0answers
23 views

Recurrence Relations- n length of old numbers

Find the recurrence relation for strings of any length such that strings have odd number of odd digits where each digit is in the range of [0,9].
1
vote
1answer
126 views

Finding recurrence relation for digits

codes have been generated odd number of odd digits. Let $ a_n $ be the number of valid n-digit activation codes. Find the recurrence relation. I can't figure out and understand the question. Can you ...
0
votes
1answer
35 views

Setting up a matrix from a recurrence relation to find diagonal matrix?

Considering the recurrence $F_n= F_{n−1}+3F_{n−2}−2F_{n−3}$ where $F_0=0$, $F_1=1$ and $F_2=2$, use diagonalization to find a closed form of the expression. If the sequence is continued the numbers ...
0
votes
2answers
21 views

Unable to verify solution to difference equation $m_x - 2pqm_{x-2} = p^2 + q^2$

I want to verify that the solution to the difference equation $m_x - 2pqm_{x-2} = p^2 + q^2$ with boundary conditions $m_0 = 0$ $m_1 = 0$ is $$m_x = -\frac{1}{2}(\frac{1}{\sqrt{2pq}} ...
2
votes
1answer
119 views

All solutions of the recurrence relation

Find all solutions of the recurrence relation $$ a_n = 2a_{n-1}+15a_{n-219}-64a_{n-3}+k $$
0
votes
1answer
24 views

Recurrence Relation, a question about the relation between $A_n$ and $A_{n+1}$

Given the following recurrence relation: $$A_{n+1} = {1 \over 4(1-A_n) }$$ $$ A_1 = 0 $$ Can I safely assume that if- $$\forall n \in \mathbb{N}, \ A_n < 1/2$$ then $$\forall n \in \mathbb{N}, \ ...
0
votes
1answer
16 views

Log property in proof of Master theorem

The family of recurrence considered is of the form $$ T(n) = aT(n/b) + n^c $$ $a,b,c$ are integers. One case of master theorem states: if $c< log_b a$, then $T(n) = \Theta(n^{log_b a}) $. I have ...
3
votes
1answer
33 views

Closed Form Solution for Recurrence Relation

Is it possible to calculate the closed form solution for the following recurrence relation? $$ T(n) = T\left(\frac{n}{2}\right) + T\left(\frac{n}{2} + 1\right) + \frac{n}{2} $$ I am trying to teach ...
0
votes
1answer
12 views

Solution Verification: turning recurrence relation into asymptotic bound with master theorem

Here are some recurrences I think I've correctly converted to bounds. Please let me know if I am right or wrong. T(n) = 3T(n/3) + lg(n) = Θ(n) T(n) = 3T(n/6) + n = Θ(n) T(n) = 4T(n/2) + n^2 = ...
1
vote
1answer
49 views

Concrete Mathematics Josephus Problem: How to prove 1.17 & 1.18

On the last page of the Josephus problem where things get really general, we're shown the pretty slick radix changing recurrence & solution 1.17 & 1.18 f(j) = aj, for 1 <= j <= d; ...
0
votes
0answers
14 views

Tips on effectively representing this recurrence relation in a generalized form.

The recurrence relation is $$ y_n = d_1 y_{n-1}+\frac{d}{dx}[y_{n-1}] $$ a good thing to note as well is $$ \frac{d}{dx}[d_n] = d_{n+1} $$ This is terrible to expand out after a good while, The main ...
1
vote
2answers
36 views

A second order problem on recurrence relation equals 3^n

I had this Recurrence Relation problem: $a_{n+2} + a_{n+1} - 12a_n = 0$ And I solved in a form like this $a_n = A(r_1)^n + B(r_2)^n$ $r^{n+2} + r^{n+1} - 12r^n = 0$ ...
0
votes
2answers
33 views

Define a sequence of integers $H(n)$ by $H(0) = 1$, $H(1) = 3$ and $H(n+1) = H(n) + H(n-1)$?

Then show that $H(n)$ can be expressed in the form $a\cdot(\psi(1))^n + b\cdot(\psi(2))^n$ and that $\psi(1)$ and $\psi(2)$ are the same numbers that occur in the proof of the Fibonacci numbers. I'm ...
0
votes
0answers
17 views

Second Order Recurrence Relation with Exogenous Forcing Sequence

I am solving an infinite horizon maximization problem, which yields as FOC second-order recurrence relation $A_{n+1} = \delta A_{n+2} + \delta A_{n} + c_n$, where $\{c_n\}_{n=0}^\infty$ and ...
3
votes
2answers
66 views

Show that it is the solution of the recurrence

I have to show that the solution of the recurrence $$X(1)=1, X(n)=\sum_{i=1}^{n-1}X(i)X(n-i), \text{ for } n>1$$ is $$X(n+1)=\frac{1}{n+1} \binom{2n}{n}$$ I used induction to show that. I have ...
2
votes
1answer
57 views

Find and solve a recurrence relation for the number of n-digit ternary sequences in which no 1 appears to the right of any 2.

Find and solve a recurrence relation for the number of n-digit ternary sequences in which no 1 appears to the right of any 2. $a_1=3$ and $a_2=8$ I am having trouble creating the recurrence relation ...
3
votes
3answers
70 views

Solve the recurrence relation $a_n=3a_{n-1}+n^2-3$, with $a_0=1$.

Solve the recurrence relation $a_n=3a_{n-1}+n^2-3$, with $a_0=1$. My solutions: the homogeneous portion is $a_n=c3^n$, and the inhomogeneous portion is $a^*_n=-1/2n^2-3/4n+9/8$. This results in a ...
0
votes
1answer
41 views

If the average of 2 successive years’ production 1/2($a_n + a_{n-1}$) is 2n + 5 and $a_0=3$, find $a_n$.

If the average of 2 successive years’ production $\frac{1}{2}(a_n + a_{n-1})$ is $2n + 5$ and $a_0=3$, find $a_n$. I started by solving for $a_n$ and got: $a_n = 4n+10-a_{n-1}$ but I am unsure how to ...
2
votes
0answers
30 views

Solve the recurrence $T(n)=aT(n-1)+bn$

I have to solve the following recurrence, given $T(1)=1$, $$T(n)=aT(n-1)+bn$$ I have done the following: $$T(n)=aT(n-1)+bn \\ =a^2T(n-2)+ab(n-1)+bn \\ =a^3T(n-3)+a^2b(n-2)+ab(n-1)+bn \\ = \dots \\ ...
5
votes
1answer
134 views

Solving a recurrence with diagonalization?

Considering the recurrence $F_n=F_{n-1}+3F_{n-2}-3F_{n-3}$ where $F_0=0$, $F_1=1$ and $F_2=2$. Use diagonalization to find a closed form expression for $F_n$. So I first continued the recurrence to ...
1
vote
2answers
50 views

The convergence of a recurrcively defined sequence.

Let $a_1=\sqrt{2}$ and $a_n=\sqrt{2+a_{n-1}}$ determine the convergence of the sequence and find its limit. I know the sequence converges to $2$ and i can show this informally. But I don't know how ...
0
votes
1answer
39 views

Solution of recurrence

I need some explanations at the proof of the following theorem. Theorem: Let $a$, $b$ and $c$ be nonnegative constants. The solution to the recurrence $$T(n)=\left\{\begin{matrix} b & ,\text{ ...
1
vote
1answer
48 views

New Identities for Generalized Fibonacci Numbers?

Over the past few months I have been investigating one the generalizations of the Fibonacci numbers, called the Generalized Fibonacci Numbers (GFNs). The GFNs are just like the regular Fibonacci ...
3
votes
1answer
37 views

A general or simple method to solve this iterative/recursive problem?

I have the following iteration $$ y_n\mapsto n\sum_{m=1}^{n+1}y_m $$ starting with $y_1$ being a positive real number. Is there a standard method to find the coeffcients of all $y_n$ after ...
1
vote
1answer
30 views

How to find the basic reproductive number of a discrete SIS epidemic model

I have been following a textbook called Mathematical Models in Population Biology and Epidemiology. The SIS model is given by the system \begin{aligned} S_{n+1} &= \Lambda + S_n e^{-\mu} ...