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

learn more… | top users | synonyms (2)

2
votes
1answer
47 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
288 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
68 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 < ...
1
vote
1answer
54 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
34 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 = ...
2
votes
1answer
39 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
76 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
28 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
26 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
46 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
52 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
2answers
58 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 ...
4
votes
0answers
51 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 ...
3
votes
1answer
248 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
28 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
162 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
29 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
585 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
84 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
32 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} ...
2
votes
0answers
57 views

Recurrence with Polynomial Coefficients of $n$

How would I solve or obtain a closed-form solution for 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 ...
0
votes
1answer
203 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
148 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, ...
1
vote
1answer
148 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
93 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
23 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}} ...
4
votes
1answer
144 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
31 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
31 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
57 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
26 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
122 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
25 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
43 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
46 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
28 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
79 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
522 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
97 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
52 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
46 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
313 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
51 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
50 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{ ...
3
votes
1answer
99 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 ...
4
votes
1answer
77 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
85 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} ...
3
votes
2answers
52 views

How does the recursion relation work in the solution to this differential equation (using series)?

Sorry for the vague title but it would not let me post the first step and last step of this equation (too many characters!). How does $$\dfrac{a_0}{3n(3n-1)(3n-3)(3n-4)\cdots 9 \cdot 8 \cdot 6 \cdot ...
2
votes
2answers
85 views

Proving $\lim _{n\to \infty }a_{n+1}=\lim _{n\to \infty }b_{n+1}$ where $a_{n+1}=\frac{a_n+b_n}{2}\:$, $b_{n+1}=\sqrt{a_n\cdot \:b_n}$

$a_1,\:b_1>0$ $a_{n+1}=\frac{a_n+b_n}{2},\:b_{n+1}=\sqrt{a_n\cdot b_n}$ The question asks to prove that: $\lim _{n\to \infty }\left(a_n\right)=\lim \:_{n\to \:\infty \:}\left(b_n\right)$. ...
0
votes
3answers
359 views

Solving Linear Recursion with backtracking

What am I doing wrong? Is there a missing step? Tried googling but cannot seem to get it. Question: $$\begin{align} a_{n} &= a_{n-1}+2n+3 ,\\ a_{0} &= 4 \end{align}$$ Things I did: ...