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

learn more… | top users | synonyms

2
votes
1answer
50 views

Techniques for solving recurrence relations using generating functions

How does one extract coefficients from generating functions that involve exponents. Things like $A(z) = 1+A(z^2)$ or $A(z)= 1+A(z^2)+A(\sqrt z)$?
1
vote
0answers
43 views

Monotonicity of a recursively defined sequence $s_{n+1} = \sqrt{4s_n -1}$

I am trying to answer this question: Let $s_1 = k$ and $s_{n+1} = \sqrt{4s_n -1}$. For what values of $k$ will the sequence $s_n$ be monotone increasing? I know the definition of monotone increasing ...
0
votes
2answers
38 views

Solving for Recurrence Function

I was reading the following http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/99-recurrences.pdf notes on recurrence relation, page 2. A recurrence function for the Tower of Hanoi is given by ...
2
votes
1answer
76 views

Define a recursive sequence for the following formula f(n) = n(n+1)

Define a recursive sequence for the following formula f(n) = n(n+1). Preferably one only defined by previous $a_n$ terms, i.e., no 'n' terms. If possible that is. So for example the following ...
1
vote
0answers
63 views

Solving a Recurrence Relation With Summation and Tau Function

How can I solve the following: $$ T(n) = \sum_{i = 1}^{d(n) - 2}T(v_i) + \sum_{i = d(n) - 1}^{n - 1}c + c' $$ Where $d(n)$ is the Tau function, and v is the set of values dividing n. e.g. $d(18) = ...
0
votes
1answer
24 views

Help with difference/recursion equation change of variable

I am in a self study of Dynamic Systems and am reading through David Luenberger's book and cannot seem to figure the following question out. Solve the difference equation using a change of variables ...
2
votes
2answers
64 views

Explicit formula for recurrence

I know how to get explicit formula for simple recurrence $a_n = m_1a_{n-1} + m_2a_{n-2}\dots$ for $m_{1,2\dots}$ being constant numbers. I'm wondering how to get explicit formula for recurrence like ...
3
votes
1answer
170 views

Estimating linearly independent solutions to third order recurrence relation

I'm trying to prove something about two linearly independent solutions; $a_n$, $b_n$, to a recurrence relation I have - specifically that $\left| \frac{a_n}{b_n} \right|$ is eventually monotonically ...
4
votes
0answers
54 views

Transform recurrence relation

Is it possible to transform following recurrence relation $a_n=4a_{n-2}-a_{n-4}$, $a_0=1$, $a_1=0$, $a_2=3$, $a_3=0$ so that it will have nonnegative coefficients? Number of terms, of course, can be ...
0
votes
2answers
30 views

Proofs by strong induction [duplicate]

I am trying to solve the following problem using strong induction, the problem is the following: For any positive integer $n$, let $T_n$ be the number $1$ if $n<4$ and the number $T_{n − 1} ...
1
vote
3answers
176 views

Recurrence of T(n) = T(n/3) + T(2n/3)

I've searched online for this but I only seem to find answers for a similar equation: T(n) = T(n/3) + T(2n/3) + cn But the one I'm trying to solve is: ...
0
votes
2answers
48 views

Ways to add a number using just 1's, 5's, 10's, 25's, 50's

given the set $\{1, 5, 10, 25, 50\}$, in how many ways, can you combine this numbers to get a specific number. For example, 11 can be shaped as $1\cdot11$, or $5\cdot112 + 1\cdot111$, or $10\cdot111 + ...
2
votes
0answers
31 views

Verify that this recurrence relation is in O(log n)

For the recurrence $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ is in $\Theta(lg n)$ My attempt at a solution (mostly just wanting to verify its correct). Lower Bound: $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ ...
1
vote
2answers
59 views

Solving this recurrence relation

Hi all I'm preparing for a midterm and the following appeared as a practice problem that I'm not quite sure how to solve. It asks to find a tight bound on the recurrence using induction $$ {\rm ...
0
votes
0answers
21 views

Recurrence formula for orthogonal polynomials

Consider the recurrence formula: $P_n(x)=(x-c_n)P_{n-1}(x)-\lambda_n P_{n-2}(x)$ The problem consist on showing that $\xi_1<c_n<\eta_1$ where $[\xi,\eta]$ is the true interval of orthogonality ...
7
votes
3answers
336 views

Why computing Fatou coordinate is so hard?

I'm trying to make images of Fatou coordinate for some polynomial maps. If I'm not wrong there is no explicit general formula/method for computing Fatou coordinate near parabolic fixed point. Is ...
0
votes
0answers
24 views

proving a recurrence relation

I'm trying to prove that the recurrence $T(n) = T(\alpha n)+T((1-\alpha)n)+n$, where $0<\alpha<\frac{1}{2}$, has an order of growth $T(n)= an$ log $n$ $\in \Theta(nlog(n))$ where $a$ is a ...
6
votes
2answers
702 views

Recursive square root problem [duplicate]

Give a precise meaning to evaluate the following: $$\large{\sqrt{1+\sqrt{1+\sqrt{1+\sqrt{1+\dotsb}}}}}$$ Since I think it has a recursive structure (does it?), I reduce the equation to $$ ...
1
vote
1answer
45 views

Recurrence Question with Ternary String

Problem: Find a recurrence relation for the number of ternary strings of length n that contain at least one 0. Ternary string only contains 0s, 1s, and 2s. Approach: Assuming that the length n is ...
1
vote
2answers
62 views

Reference Request: Difference Equations

I am taking a second course in calculus and came across sequences defined inductively, as in recursively. My teacher told the class that a general formula for the $n$th term can be obtained using a ...
2
votes
1answer
51 views

Expected Time for n Independent Prisoners to Escape

Suppose there are $n$ prisoners, and each day every prisoner independently has a probability $p$ of escaping. What is the expected length of time before all prisoners have escaped? Someone asked ...
0
votes
0answers
38 views

Multiplicative Inverse of a Power Series

For a formal power series $$F(x) = \sum p_i x^i$$ a multiplicative inverse of $F$ exists iff $p_0 \neq 0$. The inverse $\sum q_i x^i$ satisfies the recursion $$q_0 =\frac{1}{p_0}\\ q_{n} = ...
0
votes
1answer
64 views

Recurrence Relation with two variables

I am trying to solve the following recurrence relation: $T(a,b)=T(a-2^{b-1}+1,b) + T(a,b-1)$ where: $$T(a,-1)=0\\T(0,0)=0\\T(a,1)=1\\T(a,0)=1$$ I tried using Matlab and Wolfarmalpha however they ...
1
vote
4answers
83 views

Solving the recurrence relation $a_{n+1}=a_n^2$

How would one solve the recurrence relation $a_{n+1}=a_n^2$ for, say, $a_0=2$? The solution seems to be $a(n)=2^{2^n}$, but how would one get to that conclusion? Furthermore, how would one solve a ...
1
vote
0answers
48 views

Solution to a recursion relation.

Let $\beta >0 $. The question is to solve a following recursion: \begin{equation} P^{(j+2)}(\beta) = \frac{\imath}{2} \left[ \left((-1+\beta) j - 1\right) P^{(j+1)}(\beta) + ...
1
vote
0answers
33 views

Solve recurrence $a[n,k]=(2m-2k)\;a[n-1,k+1]+k\;a[n-1,k]$

I'm trying to count how many vectors of size $n$ there are, given that the elements of the vector are integers from the range $\{-m,m\}-\{0\}$ (zero is excluded), and there are no pair of elements ...
2
votes
1answer
35 views

Recurrence relation and big-O-notation

Consider the following recurrence relation: $$T(n)=c\cdot + 2\cdot T(n/2)$$ This is the recurrence relation for the Merge-Sort algorithm. How can one deduce from this equation the time complexity of ...
2
votes
1answer
49 views

Arithmetic function

An arithmetic function is defined as follows:$f(1)=1$, $f(2k)=k$ and $f(2k+1)=f(k)+f(k+1)$. When (for which $k$) is $f(k)$ even? While it is obvious that $f(4n-1)=f(4n)=2n$, therefore $f(k)$ is even ...
3
votes
1answer
167 views

How to formalize in terms of category theory?

We define a recursive map as maps, $\chi \to \xi^{'}, \, \chi^{'} \to \xi^{''}, \, \chi^{''} \to \xi^{'''}, \ldots, \chi^{n} \to \xi^{n+1} \wedge \xi \to \chi, \, \xi^{'} \to \chi{'}, \xi^{''} \to ...
0
votes
1answer
81 views

Solve a Quadratic map

I read this on Wolfram Alpha. It states that: a quadratic recurrence relation uses a second degree polynomial to express $x_{n+1}$ as a function of $x_n$. A "quadratic map", then, is a recurrence ...
0
votes
1answer
73 views

Quadratic Map Solution

I read this on Wolfram Alpha. It states that: a quadratic recurrence relation uses a second degree polynomial to express $x_{n+1}$ as a function of $x_n$. A "quadratic map", then, is a recurrence ...
0
votes
0answers
49 views

Solving the recurrence $F(0) = X$ and $F(i)=A \cdot (F(i-1))^2 + B \cdot F(i-1) + C$

Moderator Note: This is a current contest question on codechef.com. I am given $F(0)=X$ and $F(i)=A \cdot (F(i-1))^2 + B \cdot F(i-1) + C$ for $1 \leq i \leq N$. Now given $N,A,B,C$ and $X$, how ...
0
votes
2answers
51 views

Show that there is a unique sequence of positive integers $(a_n)$ satisfying $a_1=1,a_2=2,a_4=12,a_{n+1}a_{n-1}=a_n^2\pm 1 $

Show that there is a unique sequence of positive integers $(a_n)$ satisfying the following conditions. $$a_1=1,a_2=2,a_4=12,a_{n+1}a_{n-1}=a_n^2\pm 1$$ I approached the problem to find out, ...
1
vote
0answers
23 views

Analyzing a recurrence model: equilibriums, stability and periodic behavior.

In orer to increase my knowledge in math I decided to analyze the following recurrence relation (logistic growth in ecology) $$N(t+1) = N(t) (1 + r(1-\frac{N(t)}{K}))$$ I found the equilibriums by ...
2
votes
2answers
101 views

A sequence in which $x_n$ depends on all of $x_0, … x_{n-1}$

A particular combinatorial sequence I was looking at turned out to obey the following pair of recurrence relations: $$N_{2n+1}=\sum^n_{k=0}N_{2k}$$ ...
1
vote
0answers
61 views

May someone tell me where I went wrong when finding a closed-form solution to a recursion?

Let $r(n)=\left\lceil\frac{n}{4}\right\rceil$, where $k \in \mathbb{N}$. Note that this can be rewritten as a recursion $R(n)=R(n-4)+1$, where, $R(0)=0, R(1)=1, R(2)=1, R(3)=1$. Since this recursion ...
-1
votes
2answers
151 views

how to find nth term of different fibonacci series with golden ratio [duplicate]

what i know : if i want to find $Nth$ term of a fibonacci series like : 1 1 2 3 5 8 13 21 ....... then to find $6th$ term we use golden ratio ...
0
votes
0answers
28 views

Convergence to closed curve in complex plane

The recurrence relation $$f_n=\frac{(f_{n-2})^{f_{n-2}}-(f_{n-1})^{f_{n-1}}}{2}$$ with initial condition $f_0=0$ and $f_1=.1+.1i$ does not converge to a fixed value of $f_n$ for large $n$, but it ...
1
vote
2answers
41 views

Find a recurrence for in , the number of integer compositions of n which only have 1s and 2s as parts.

Find a recurrence for $$i_n$$ the number of integer compositions of $n$ which only have $1$s and $2$s as parts. How do you approach this problem?
0
votes
0answers
46 views

Linear Constant Coefficient Different Equation

The question I have is about linear constant coefficient question but I don't really know for sure how to do it. The question is: Suppose that $N_{m+1}-N_m=f(N_m,N_{m-1})$.(a) How would you determine ...
9
votes
1answer
302 views

Prove that this particular sequence contains an infinite number of sixes

Given the sequence $$2,7,1,4,7,4,2,8,\ldots$$ which begins with $2, 7$ and is constructed by multiplying successive pairs of its members and adjoining the results as the next one or two members of ...
0
votes
0answers
46 views

$(x\cdot\frac{d}{dx})^n$ resulting in a 3D recurrence relation

I am trying to find the solution to $$\left(x\cdot\frac{d}{dx}\right)^n\cdot f(x)$$ I first assumed the solution to be of the form $$\left(x\cdot\frac{d}{dx}\right)^n\cdot ...
0
votes
2answers
98 views

Does this series $2 + 4 + \cdots + \sqrt{\sqrt{n}} + \sqrt{n} + n$ have a general term?

Does this sum simplify to a general term in terms of $n$? If so, how would you arrive at that term? $2 + 4 + \cdots + \sqrt{\sqrt{n}} + \sqrt{n} + n$. Thanks.
0
votes
3answers
82 views

walking along the number line

Suppose you start walking along the number line from $0$ to $100$, moving $1$ position to the right in each step. There are some shortcuts $(i,j)$ where $i,j\in[0,100]$ and $i<j$. If you step on ...
0
votes
1answer
27 views

Recursive Algorithm Analysis

$$T(n) = 2\cdot \sqrt{n} \cdot T(\sqrt{n}) + \Theta (\lg n)$$ I have been trying to solve this question but I could not find anything. My approach: $n = 2^k$ $S(k) = T(2^n)$ and $S(k/2) = ...
0
votes
1answer
40 views

How to prove this theorem?

Let Un be the number of words with length $n$ in the alphabet ${0,1}$ that have the property of not having consecutive zeros. Prove that: $$U_1 = 2, U_2= 3, U_n = U_{n-1} + U_{n-2}.$$ I am stuck ...
0
votes
2answers
121 views

Upper and Lower bounds for the function

Please find the upper and lower bounds of the recurrence relations. $T(n)= 4T(n−2) + 6T(n-3) + 3^n $ if $n>=3$ $T(n)= 1 $ if $ n <=2$ I am confused. Thanks a lot :)
0
votes
1answer
51 views

Elementary Functions Name: f(a,b) = f(b,a-1)+b

I am quite simply looking for a function that I forgot about from way back when. I am positive I learned this at some point in grade school, but I just can't remember what it is called! The function ...
3
votes
3answers
185 views

Proof Using the Monotone Convergence Theorem for the sequence $a_{n+1} = \sqrt{4 + a_n}$

Consider the recursively defined sequence $a_0 = 1$ $a_{n+1} = \sqrt{4 + a_n}$ How to prove that the sequence converges using the Monotone Convergence Theorem, and find the limit?
0
votes
1answer
39 views

Verify if T(n) = T(n/2) + log(n) - Recurrence Relation

I'm not sure if I'm correct, but could you please verify if this is right: $$\begin{align} T(n) &= T\left(\frac{n}{2}\right) + log_{2}(n)\\ T(n) &= T\left(\frac{n}{2^{i}}\right) + ...