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

learn more… | top users | synonyms (2)

0
votes
1answer
39 views

Recursion Relation Problem: Counting Database Identifiers Recursively

A valid database identifier of length $n$ can be constructed in three ways: • Starting with $A$ and followed by any valid identifier of length $n − 1$. • Starting with one of the two-character ...
0
votes
1answer
68 views

How can I find the order of growth of this recurrence: $T(n) =\sqrt{n}T\bigl(\sqrt{n}\bigr) + n$

I am trying to find the order of growth ($O(n)$, $O(n\log n)$) of the recurrence $T(n) = \sqrt{n} \cdot T\bigl(\sqrt{n}\bigr) + n$. I started to unroll the recurrence and found that I can rewrite it ...
0
votes
0answers
47 views

$T(n) = 4T({n/2}) + n \log{n}$ using substitution method

can you help me please with solving recurrence $T(n) = 4T({n/2}) + n\log{n}$ by substitution method? By using Master theorem I know the result is $\theta(n^2)$. So I need to prove that $T(n) \leq ...
1
vote
2answers
48 views

Example of recurrence relation without closed form expression?

Can give an example of a recurrence relation for which there does not exist a closed form expression?
4
votes
2answers
47 views

If $f_1(k)=\sum_{i=1}^k\frac{1}{i}$ and $f_n(k)=\sum_{i=1}^kf_{n-1}(i)$, then what is $f_n(n)$?

Let $$f_1(k)=\sum_{i=1}^k\frac{1}{i},$$ and define inductively $$f_n(k)=\sum_{i=1}^kf_{n-1}(i).$$ So, $$f_2(k)=\sum_{i_2=1}^k\sum_{i_1=1}^{i_2}\frac{1}{i_1},\quad ...
1
vote
4answers
72 views

Recurrence Relation $k_{n+2}=\frac{1-n}{n+2}k_n$

There was an interesting question posted on here earlier today but it seems to have disappeared. With due to respect to the OP, I'll post the same question here from memory. If anyone finds the ...
2
votes
0answers
53 views

How to solve this tough recurrence relation?

For solving a related probability problem, I'm required to solve the following recurrence relation:- $q(r,b,L)=\frac{b}{r+b}q(r,b-1,L)+\sum_{k=1}^{L}\frac{r}{r+b}\times\cdots \times ...
2
votes
1answer
22 views

recurrence relation sequence..stuck

Q-->Find a recursive solution for $S_n$ the number of sequences of length $n$, composed of the letters $a$, $b$ or $c$ in which no sequence contains consecutive b's. Give detailed explanations. what ...
0
votes
2answers
42 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
49 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 ...
1
vote
1answer
88 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 ...
1
vote
0answers
58 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
1answer
39 views

Proof by induction that if $a_0 = 1$ and $a_n = n + 2 a_{n-1}$, then $a_n \ge 2^n + n^2$.

I have that $a_0 = 1$ and $a_n = n + 2 a_{n-1}$ for $n \geq 1$. Now I need to proof by induction that $a_n \geq 2^n + n^2$. I already have my base case. My hypothesis would be $a_{n-1} \geq 2^{n-1} ...
0
votes
0answers
16 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
150 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 ...
3
votes
2answers
32 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
82 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
38 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
36 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) = ...
-9
votes
2answers
186 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
63 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
37 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
27 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
34 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
52 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
24 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
21 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
44 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
37 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
47 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
13 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
34 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
65 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
49 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
26 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
265 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
40 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} ...
2
votes
0answers
34 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
105 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
41 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
132 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
51 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}} ...
3
votes
1answer
126 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
19 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
38 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 ...