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

learn more… | top users | synonyms

3
votes
1answer
125 views

Sums of Fibonacci numbers

Given a multiset S of integers, when is $$\sum_{s\in S}F_{n+s}=kF_{n+t}$$ for some integers k and t and all integers n? $F_n$ is the n-th Fibonacci number. Essentially, given a sum of Fibonacci ...
1
vote
0answers
152 views

Achieving the “mirror” of exponential decay

I'm working on a product that has a visual transition. I've found that applying a simple filter that results in an exponential decay (starting fast, then tapering off) is pleasing in one direction. ...
3
votes
2answers
468 views

solving recurrence relations

As I know for solving recurrence relation like this $$a(n) = Aa(n-1)+B a(n-2)$$ we are trying to solve quadratic equation like this $$s^2-A \cdot s-B=0$$ Consider three cases Two distinct ...
3
votes
1answer
836 views

Dyadic Expansion-Proof?

Working through a measure theory textbook, and would like to understand dyadic expansions before I can understand its connections with the law of large numbers. I want to see this proved in detail, ...
3
votes
3answers
458 views

expansion of $\cos^k(\theta)$

Does any body know a expansion of : $\cos^k(\theta)$ in function of $\cos$ and/or $\sin$ but without power? For example : $\cos^2(\theta)=\frac{1}{2}(\cos(2\theta)+1)$, but i would want a ...
5
votes
2answers
1k views

Solving recurrence $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n)$

I'm learning algorithms by myself and am using the excellent Introduction to algorithms to do that. It has been quite a long time since I last studied math, so maybe the solution to my problem is ...
5
votes
1answer
156 views

general technique to convert recurrence relation to integral

I know the following recurrence relation $$a_n=\frac{a+na_{n-1}}{a-n}$$ with $a_0=1$ can be represented alternatively as an integral $$a_n=a\int_0^1{x^{a-n-1}(2-x)^ndx}$$ Verifying this is easy, ...
4
votes
2answers
458 views

Solving recurrences of the form $T(n)=aT(n/a)+Θ(nlgn)$

On pages 95 and 96 of the third edition of the CLRS book, we find the following, which applies here since $a=b$ is all it takes to block the application of the Master Theorem: "Although $n\lg n$ is ...
3
votes
1answer
199 views

Identifying recursive polynomials

I need to evaluate the following function and want to proceed analytically as far as possible: $F(y) =e^{ i \beta \left ( y \frac{d}{d y} \right )^2} y \, e^{-y^2/2}$ My plan is to expand into ...
0
votes
1answer
146 views

Modelling a difference equation question?

Stuggling with this one: In a simple economic model, time t is set up as a discrete parameter (possibly referring to days or months), while demand $D_{t}$ and supply $S_t$ are described in terms of ...
2
votes
2answers
88 views

Is this recurrence $O(n^2)$?

Is this recurrence $O(n^2)$? $$ \begin{cases} T(1) = a\\ T(n+1) = T(n) + \log_2(n), n\geq 1 \\ \end{cases} $$ I try to solve it like this: $T(n+1) = T(n) + \log_2(n), n \geq 1 $ $T(n+1) - ...
4
votes
2answers
295 views

What is the closed form of this recurrence relation

I have the following recurrence relation : $$g(0) = c $$ $$g(i+1) = g(i) + (1-g(i))*g(i)^{2}$$ where 0 < c < 1. Is there any closed form for this relation? If not can you give me an upper ...
2
votes
0answers
142 views

Solving the recurrence relation $a_n = \frac{g}{1-ga_{n-1}}$ [duplicate]

Possible Duplicate: Help on a rational recursive relation: $T[n+1]=\frac{E[n+1](D+T[n])}{E[n+1]+D+T[n]}$ I'm trying to understand how one solves the recurrence relation in the title: $a_n ...
1
vote
1answer
203 views

Matrix recurrence equation

We define a $"2 \times 2"$matrix $A$. The following recurrence equation is given:$$A^{k+1}=\frac{A^k}{k}+I,(k=1,N)$$where $I$ is the identity matrix. How can I find the matrix $A$? Thanks
2
votes
3answers
523 views

generalised formula for sum of first $n$ tetranacci numbers

In the case of Fibonacci numbers, the formula for the sum of first $n$ numbers of the series is $f(n+2)-1$, but in the case of tetranacci numbers I am unable to arrive at such formula. Thanks.
4
votes
2answers
218 views

Help on a rational recursive relation: $T[n+1]=\frac{E[n+1](D+T[n])}{E[n+1]+D+T[n]}$

I am trying to solve this rational recursive relation: $$T[n+1]=\frac{E[n+1](D+T[n])}{E[n+1]+D+T[n]}$$ where $T[1]=\frac{E[1]*D}{E[1]+D}$ for constant $D>0$ and $E[n]>0$. When $E[n]$ is ...
17
votes
2answers
860 views

Self-avoiding walk on $\mathbb{Z}$

How many sequences $a_1,a_2,a_3,\dotsc$, satisfy: i) $a_1=0$ ii) ($a_{n+1}=a_n-n$ or $a_{n+1}=a_n+n$) iii) $a_i\neq a_j$ for $i\neq j$ iiii) $\mathbb{Z}=\{a_i\}_{i>0}$ Are the two alternating ...
1
vote
2answers
889 views

prove a monotonically increasing function from recurrence relation by induction

How to prove $T(n)$ is a monotonically increasing function by induction provided that $T(n) = T(n/2 + \sqrt{n}) + \sqrt{6046}$? $n$ is larger than $n/2 + \sqrt{n}$ when $ n \geq 5$ and it is ...
7
votes
2answers
256 views

q-Analogue of the formula $x^n=\sum_k\left\{n\atop k\right\}(x)_k$.

The stirling numbers of the second kind satisfy the formula $x^n=\sum_k\left\{n\atop k\right\}(x)_k$, where $(x)_k$ is the falling factorial. Consider the $q$-analog recursive definition of the ...
5
votes
0answers
511 views

The Average Running Time Of Euclid Algorithm?

What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$? It seems very hard to deduce from the recurrence $T(m,n) = T(n, m ...
3
votes
4answers
1k views

Recurrence - Master Theorem - Asymptotic Question

Sorry if this question has been asked before, but I am trying to figure this out. I am using the CLRS text, Introduction to Algorithms. In the Recurrences chapter, in the Master Theorem section, the ...
2
votes
1answer
1k views

Proving a recurrence relation with induction

I've been having trouble with an assignment I received with the course I am following. The assignment in question: Use induction to prove that when $n \geq 2$ is an exact power of $2$, the solution ...
2
votes
0answers
439 views

recurrence relation with non constant coefficients

I'm trying to solve a second order differential equation and I got a recurrence. Can someone help to solve $$n(n-1+q)a_{n}-a_{n-3}+e\cdot a_{n-2}=0$$ where $q$, $e$, and $a_{0}$ are some real numbers ...
4
votes
2answers
285 views

Recurrence for $q$-analog for the Stirling numbers?

I read in some papers that the Stirling numbers (of the second kind) have a natural $q$-analog $S_q(n,k)$, which satisfy the recurrence $$ S_q(n,k)=(k)_qS_q(n-1,k)+q^{k-1}S_q(n-1,k-1) $$ with the ...
1
vote
3answers
157 views

Solving a recurrence related to tree counting

What I want is to count the number of binary trees on $n$ nodes, except when a node has only one child, I don't distinguish between left and right. So let $T_n$ be the number of such trees on $n$ ...
0
votes
3answers
495 views

can we use generating functions to solve the recurrence relation $a_n = a_{n-1} + a_{n-2}$, $a_1=1$, $a_2=2$?

I have this question. Can we use generating functions to solve the recurrence relation $$\begin{align*} a_1 &= 1,\\ a_2 &= 2,\\ a_n &= a_{n-1} + a_{n-2} \end{align*}$$ Thanks
4
votes
2answers
166 views

Count the number of divisions of a set recursively

I'm trying to understand the reasoning behind the answer to the following question from an old exam. Given a set $S_n = \{ 1, 2, 3,\dots n\}$ find how many divisions, $K_n$, there are of the set ...
0
votes
2answers
3k views

$T(n)=3T(n/2) + n\log n,\ T(1)=1$ [duplicate]

Possible Duplicate: $T(n) = 4T({n/2}) + \theta(n\log{n})$ using Master Theorem What is the order of this recurrence? $$T(n)=3T(n/2) + n\log n,\ \ T(1)=1$$ I found the answer where ...
5
votes
1answer
232 views

A nicer recurrence for the Eulerian polynomials.

I was perusing the subject of Eulerian polynomials. I'm assuming the definition that the Eulerian polynomial is defined by $C_n(t)=\sum_{\pi\in S_n}t^{1+d(\pi)}$, where $d(\pi)$ is the number of ...
0
votes
2answers
140 views

Sum of Lucas Numbers

I'm having trouble writing the statement of $L_n = \alpha^n + \beta^n \forall n\geq 1$ $$\sum_{i=1}^n L_n = \alpha^n + \beta^n$$ Any ideas?
7
votes
3answers
1k views

Solving a Recurrence Relation/Equation, is there more than 1 way to solve this?

1) Solve the recurrence relation $$T(n)=\begin{cases} 2T(n-1)+1,&\text{if }n>1\\ 1,&\text{if }n=1\;. \end{cases}$$ 2) Name a problem that also has such a recurrence relation. The ...
12
votes
2answers
497 views

Zeroes of the third derivative of an iterated sine.

I've been playing with the functions $$f_n:[0,\pi/2]\to[0,1]\\\begin{cases} f_1&=&\sin\\f_{n+1}&=&\sin\circ f_n\end{cases}.$$ A simple argument proves that $f_n(x)\to 0$ for $x\in ...
2
votes
0answers
66 views

On bounding the average cost of top-down merge sort

Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that $$ A_0 = A_1 = 0;\quad A_n = ...
2
votes
3answers
1k views

how to work out a closed form of a sequence

Consider the following linear recurrence sequence. $x_1 = 11$, $x_{n+1} = -0.8x_n + 9,\quad n = 1,2,3, \ldots.$ Find a closed form for this sequence.
2
votes
1answer
1k views

$T(n) = 4T({n/2}) + \theta(n\log{n})$ using Master Theorem

I am trying to solve the following recurrence relation using the master theorem: $$T(n) = 4T({n/2}) + \theta(n\log{n})$$ So: $a = 4$, $b = 2$, and $f(n) = n\log{n}$ So we are comparing: ...
1
vote
3answers
2k views

Solving recurrence relation $T(n) = 2T(n - 1) + \Theta(n)$ using the recursion tree method

I am trying to solve this recursive relation using the recursion tree method: $T(n) = 2T(n - 1) + \Theta(n)$ with $T(0) = \Theta(1)$. The answer is $T(n) = 2^n*{\rm constant}_2 + (2^n - 1)n + ...
2
votes
4answers
245 views

How to solve the recurrence relation $T(n) = 2T(\frac{2n}{3})$, where $T(0) = T(1) = 1$?

Please explain the most elementary method of solving this recurrence relation: $$ T(n) = 2T\left(\left\lfloor\frac{2n}{3}\right\rfloor\right)$$ where $T(0) = 0$ and $T(1) = 1$.
10
votes
1answer
294 views

Using Dyson's conjecture to give another proof of Dixon's identity.

For natural numbers $a_1,\dots,a_n$, Freeman Dyson conjectured (and it was eventually proven) that the Laurent polynomial $$ \prod_{i,j=1\atop i\neq j}^n\left(1-\frac{x_i}{x_j}\right)^{a_i} $$ has ...
5
votes
1answer
263 views

Recurrence for perfect matchings revisited.

I like to study combinatorics a bit as a hobby, and recently a question I found interesting was posed asking to derive a recurrence for the generating function $G_n(x)$, the ordinary generating ...
1
vote
0answers
140 views

recurrence relation of general difference polynomials

I have a sequence of difference polynomials (which I obtained by the method of finite differences) and I would like to find out if there is a recurrence relation between them. The generating function ...
3
votes
3answers
269 views

How to solve the recurrence $T(n) = \frac{n}{2}T(\frac{n}{2}) + \log n$

I am trying to solve the recurrence below but I find myself stuck. $T(n) = \frac{n}{2}T(\frac{n}{2}) + \log n$ I have tried coming up with a guess by drawing a recurrence tree. What I have found is ...
3
votes
2answers
96 views

recursive relation with sequences

I am not sure how to properly do this question but I am told that the solution I came up with is wrong and I dont see how...I basically used algebra and plugging of variables and rearranging ...
0
votes
2answers
138 views

recursion question

I just need a hint to solving this question or a starting point because I am totally stuck...I don't really understand how I can prove this. It doesn't seem possible to me that different applications ...
0
votes
1answer
539 views

Solving recurrence relation with unrolling technique

I tried to solve below recurrence relation with unrolling technique. $A({n})=4A(\lfloor{n/7} \rfloor)+n^2$ for $n\ge 2$ $A({n})=1$ for $0\le n\le 1$ What I have come up so far is $A(n) = ...
0
votes
3answers
537 views

Solving Simple Recursive Equations

For recursive equations of the form $au_{n+2}=bu_{n+1}+cu_n$ I read that the trick is to let $u_n=\lambda^n$ for some $\lambda$ and then find an appropriate $\lambda$ that fits the initial conditions. ...
2
votes
4answers
1k views

Finding the limit of a recursive sequence $x_{n+1}=\frac{1}{2}(x_{n}+\frac{M}{x_{n}})$

Define the sequence $\{x_n\}_{n\in\mathbb{N}}$ by $$x_0=\frac{M}{2}, \qquad x_{n+1}=\frac{1}{2}\left(x_{n}+\frac{M}{x_{n}}\right)$$ where $M\in\mathbb{R}$, $M\geq 0$. Find ...
2
votes
3answers
461 views

A binet-like formula for $\small 1 , 2 , 3 , 6 , 9 , 18 , 27, 54, 81, \ldots $?

This is more a "recreational" problem. By another question I came to the question for a closed-form-formula for this sequence $\small 1 , 2 , 3 , 6 , 9 , 18 , 27, \ldots $ which is just the mixture of ...
0
votes
2answers
222 views

a simple recurrence problem

Here's the problem: 1.Find a recurrence relation for the number of ways to climb n stairs if the person climbing the stairs can take one, two, or three steps at the time. 2.Explain how the relation ...
30
votes
3answers
615 views

Very curious properties of ordered partitions relating to Fibonacci numbers

I came across some interesting propositions in some calculations I did and I was wondering if someone would be so kind as to provide some explanations of these phenomenon. We call an ordered ...
0
votes
1answer
192 views

Recursive algorithm substitution?

I'm working through a problem set through MIT's OpenCourseWare and am having some trouble with recurrences. The problem is 1-2d: Give asymptotic upper and lower bounds for $T(n)$ in each of the ...