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

learn more… | top users | synonyms (2)

0
votes
2answers
33 views

Number of ways to color a sequence of squares so that no two black squares are adjacent

A sequence of squares may be colored so that each square is black or white. Let $S_n$ be the number of ways of coloring the sequence so that no two black squares are adjacent. Find a recursive ...
0
votes
1answer
41 views

Understanding a recurrence relation

I want to understand the following recurrence relation from https://oeis.org/A140993. I see the triangle it creates, but I don't understand how to generate the triangle from the formula. Can someone ...
2
votes
1answer
52 views

Finding matrix for given recurrence [closed]

For the recurrence relation: $f(0)=1$ $f(1)=1$ $f(2)=2$ $f(2n)=f(n)+f(n+1)+n$ $f(2n+1)=f(n)+f(n−1)+1$ How to find square matrices $M_0, M_1$ and vectors $u, v$ such that if the base-2 expansion ...
0
votes
0answers
50 views

Solution of $x_{k+1} = x_{k} (a x_{k} + b)$

Could anyone help me to solve the equation $x_{k+1} = x_{k} (a x_{k} + b)$, for find the explicit solution of $x_{k}$? BTW. Do you know a GOOD book for the classification for non linear difference ...
0
votes
0answers
9 views

Has anyone come across a non-constant population SIR model with infected birth?

I've come up with a seemingly new type of SIR model for one of my classes which allows for non-constant population and infected members to birth more infected members (such as is the case for many ...
0
votes
2answers
34 views

Recurrence relation rabbit population

A young pair of rabbits (one of each sex) is placed on an island. A pair of rabbits does not breed until they are 2 months old. After they are 2 months old, each pair of rabbits produces another ...
2
votes
2answers
28 views

Solve the recurrence relation by taking the logarithm of both sides and making the substitution $b_n = \lg a_n$

Solve this recurrence relation: $$a_n = \left(\frac{a_{n-2}}{a_{n-1}}\right)^{\frac{1}{2}}$$ by taking the logarithm of both sides and making the substitution $$b_n = \lg a_n$$ A couple years ago ...
1
vote
1answer
41 views

Recurrence relation to find ternary strings that do not contains 3 consecutives 0's

I'm stuck and I can't find this recurrence relation which is : Find a recurrence relation that count the number of ternary strings $(0,1,2)$ of length n that do not contains three consecutives 0's. ...
1
vote
2answers
28 views

Solve the linear homogeneous recurrence relation with constant coefficients

$$9a_{n} = 6a_{n-1}-a_{n-2}, a_{0}=6, a_{1}=5$$ So $$x^n = (6x^{n-1}-x^{n-2})\div9$$ thus $$[x^2 = (6x-1)\div9] \equiv [x^2 - \frac{2}{3}x + \frac{1}{9} = 0], x=\frac{1}{3}$$ also ...
2
votes
1answer
30 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) = ...
-6
votes
2answers
122 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
57 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
30 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
16 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
27 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
44 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
16 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 ...
0
votes
0answers
36 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
20 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
10 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
42 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
6 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
31 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
28 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
25 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
23 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
18 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 ...
5
votes
1answer
180 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$ $f(2n+1)=f(n)+f(n-1)+1$ (the first numbers of the sequence are: 1, 1, 2, 3, 7, 4, 13, 6, 15, 11, 22, 12, 25, 18, 28) ...
1
vote
2answers
26 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 ...
0
votes
0answers
23 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} ...
0
votes
0answers
17 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
87 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
18 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
22 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
115 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
34 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
18 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}} ...
1
vote
1answer
107 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
0answers
12 views

Problem in understanding the proof of master theorem case

I am going through the proof of master method or master theroem. This is the formula that is been given by the author for the Total Work =Cn^d*(∑(a/b^d)^j) where value of J=0 to logbn as per the ...
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
14 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 ...
2
votes
1answer
22 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
11 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
32 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
12 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
34 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
32 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
15 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
63 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 ...