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

learn more… | top users | synonyms

1
vote
0answers
58 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
20 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
56 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
157 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 ...
-1
votes
0answers
41 views

What is wrong with this induction proof for a closed form recursive function?

I need some help, I can't seem to find What is wrong in this proof, yet I'm not getting what I need. Anyone know? Prove by induction $2(S(2^{k-1})) + 2^k = 2(2^{k-1})k +2^k$, given that: $S(2^0 ) = ...
4
votes
0answers
47 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
27 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} ...
0
votes
1answer
31 views

What is the recurrence relation of $T(n) = c \cdot T(n^{\frac{1}{2}}) + n$ when $c>0$ and is a constant? [closed]

Trying to figure our what is the recurrence relation of $T(n) = c \cdot T(n^{\frac{1}{2}}) + n$ when $c>0$ and is a constant? Thanks to all helpers!
0
votes
3answers
62 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
33 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
20 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
42 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
18 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 ...
6
votes
3answers
305 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
17 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
356 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
votes
0answers
60 views

Recurrence t(n)=csqrt(n)+n

I'm having some trouble with this recurrence. $T(n)$= c$T(\sqrt{n}$) +n This is how i tried to solve it: $2^m= n, n= \log m$ $T(2^m)=cT(2^{m/2})+2^m$ switching $T(2^m)$ with $S(m)$ gives us ...
1
vote
1answer
36 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
39 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
45 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
28 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
56 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
73 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
41 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
30 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
32 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 ...
1
vote
1answer
44 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
159 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
47 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
58 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
45 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
40 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
19 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
72 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
58 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
68 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
22 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
39 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
37 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
282 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
44 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
97 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
76 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
19 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
68 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
46 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 ...
4
votes
3answers
115 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
31 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) + ...
2
votes
2answers
50 views

Uniform convergence of matrix integral sequence

I was given recursively defined: $M_k=I+\int_{t_0}^tA(s)M_{k-1}(s)~ds$ and $M_0=I$ and that $A(t)$ is a matrix with entries that are continuous functions on $t_0\leq t\leq t_1$. By induction we can ...