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

learn more… | top users | synonyms

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
83 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
50 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
107 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
162 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
42 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
304 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
28 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
127 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
197 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
42 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
3answers
74 views

Uniform convergence of matrix integral sequence

I was given recursively defined: $$ M_k(t)=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 ...
0
votes
0answers
37 views

Finding general solution to a non-linear discrete time recurrence relation

I am faced to a non-linear discrete time reccurence relation and I can't find the general solution. The first question is: Is there a general recipe for finding the general solution to non-linear ...
1
vote
1answer
63 views

forming difference equation

there is a square with $60$ equal blocks. If a mosquito(bug)is set to fly starting at block $1$, it is equally likely to fly to other blocks. what is the probability after $n$ flies, the mosquito is ...
1
vote
2answers
157 views

Asymptotic solution of recurrence equation

I need help to find asymptotic solution of this recurrence equation $T(n)=\sqrt{n}T(\sqrt{n})+cn$ where $c$ is constant.
3
votes
1answer
98 views

Looking for the recurrence relation for certain trigonometric integrals

By assuming that: $$ \int_{\pi/4}^{\pi/2} \frac{\cos^4(x)}{\sin^5(x)}\,dx = k,$$ what does the integral $$ \int_{\pi/4}^{\pi/2} \frac{\cos^6(x)}{\sin^7(x)}\,dx$$ equal in terms of k? I have ...
5
votes
3answers
157 views

How to solve this recurrence $T(n)=2T(n/2)+n/\log n$

How can I solve the recurrence relation $$T(n)=2T\left(\frac n2\right)+\frac{n}{\log n}$$? I am stuck up after few steps.. I arrive till $$T(n) = 2^k T(1) + \sum_{i=0}^{\log(n-1)} ...
0
votes
1answer
34 views

How does substituting $\log{n}$ in help me solve this recurrence?

I solved the recurrence $T(n) = T(\sqrt[4]{n}) + 1$, $T(2) = 1$ through thinking it through. $T(n) = O(\log{\log{n}})$ since the number of times we add 1 is the number of times we can take the 4th ...
3
votes
2answers
83 views

Is there a closed-form solution to this recurrence?

A friend and I were examining polynomials of the form $p_n (x) = x (x+1) (x+2) \cdots (x+n -1)$ and we were trying to come up with some kind of closed form for the coefficients when the polynomial is ...
2
votes
1answer
72 views

Combinatorics on letters

How many "words" of length n is it possible to create from {a,b,c,d} such that a and b are never next to each other?
2
votes
1answer
65 views

Generating Function for Recurrence Relation in 2 Variable

I have a recurrence relation with 2 variables similar to $$ F(n,m) = n\cdot F(n-1,m) + (n-m)\cdot F(n-1,m-1) $$ I want to know the steps required to get the generating Function for such recurences. I ...
2
votes
1answer
48 views

Solving the recurrence relation $T(n) = (n+1)/n*T(n-1) + c(2n-1)/n, T(1) = 0$

I tried a lot of different methods. Not able to make out the series. Could anyone help me i this regard? $ T(n) = \frac{(n+1)}{n}T(n-1) + c\frac{(2n-1)}{n} , T(1) = 0 $
0
votes
1answer
26 views

Changing recurrence to matrix

$$F(x) = aF(x-k+1) + bF(x-k+2) + cF(x-k+4) + dF(x-k+7)$$ where $F(x) = 1$ if $x<k$. $a,b,c,d,k$ are known (and positive) and $x$ is chosen. Can anyone show how to set this up in matrix form ...
1
vote
1answer
52 views

How to convert this equation into a matrix form

$$F(x)=aF(x-k+1)+bF(x-k+2)+cF(x-k+4)$$ where $F(x)=1$ if $x<k$. $a,b,c,k$ are known (and positive) and $x$ is chosen. I want to solve this recurrence using a matrix but don't really know how to ...
6
votes
6answers
598 views

How to find the limit of this recurrence relation?

$a_n$ is a sequence where $a_1=0$ and $a_2=100$, and for $n \geq 2$: $$ a_{n+1}=a_n+\frac{a_n-1}{(n)^2-1} $$ I have a basic understanding of sequences. I wasn't sure how to deal with this recurrence ...
0
votes
2answers
31 views

Can I write a Non Homogenerous equation as homogenous

Say I have Fibonacci R.Relation, $$ r^2=r+1 $$ Can I write it as $r^2-r-1=0$? From what I know a homogeneous equation is an equation equated to zero.
1
vote
1answer
61 views

Solving Recurrence Relation by Generating Function Method

Im trying to solve an-7a(n-1)+10a(n-2) Im at the point where ∈aX^n-7∈a(n-1)X^n+10∈a(n-2)x^n=0 (terms of n are subscript) After this step it is given as replace the infinite sum by an expression ...
1
vote
1answer
321 views

Solving the recurrence $T (n) = \sqrt{n} T(\sqrt{n}) + O (n)$ [duplicate]

I want to show that the requrrence $T (n) = \sqrt{n} T(\sqrt{n}) + O (n)$ is in $O(n \log \log n)$ Here's my attempt: If we expand the recursion tree, at a level $i$, there are $n^{1/2^k}$ ...
1
vote
3answers
99 views

How to go about solving this recurrence relation?

In my discrete math class we were given the problem of finding an explicit formula for this recurrence relation and proving its correctness via induction. $$a_n=2a_{n-1}+a_{n-2}+1, a_1 = 1, a_2=1.$$ I ...
0
votes
0answers
32 views

Recurrence relation by expansion

I'm trying to find a general formula for the following recurrence relation: for n of the form 2^2^k S(n) = (rootn)(S(rootn))+n S(2) = 1 First, I let b = 2^2 just for readability ...
0
votes
0answers
48 views

Removing the Summation (Closed Form)

The following question from "Combinatorics of Permutations" : $$ E[X] = \sum\limits_{k = 2}^n \frac{k\cdot T(n,k)}{n!} $$ where $$ T(n,k) = k \cdot T(n-1, k) + 2 \cdot T(n-1, k-1) + (n-k) \cdot ...
0
votes
1answer
29 views

Solving thus summation

$F_1 = 1, F_2 = 2, F_i = F_{i - 1} + F_{i - 2} (i > 2)$. A new number sequence $Ai(k)$ by the formula: $A_i(k) = F_i × i^k (i ≥ 1)$.I need to calculate the following sum: $A_1(k) + A_2(k) + ...
1
vote
3answers
56 views

solve the non homogeneous recurrence relation

These recurrences should be simple to solve but I see a ton of different ways to do it, such as general solution, particular solution etc. We did not talk about these in class, just need to get the ...
0
votes
0answers
13 views

General expression for this reccurent derivative?

I stumbled upon a problem that can be distilled to: Let $\Delta_m(x)$ be some function that depends on $x$ such that $$ \delta_{x}\Delta_m(x) = \Delta_{m+1}(x)$$ where $\delta_{x} $ is the ...
1
vote
3answers
182 views

Recurrence relations (Big-O notation)

Say I'm given a recursive function such as: function(n) { if (n <= 1) return; int i; for(i = 0; i < n; i++) { function(0.8n) } } ...
0
votes
0answers
18 views

How to solve this recurrence relation consisting of 9 equations (one of them with a minimum function)?

Given the recurrence relation as follows. $T_{k}=min((W_{k}+Y_{k}) , (X_{k}+Z_{k}))$ $A_{k}=T_{k}\frac{W_{k}}{W_{k}+Y_{k}}\frac{X_{k}}{X_{k}+Z_{k}}$ ...