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

learn more… | top users | synonyms

1
vote
1answer
101 views

Recovering two first terms from sequence $f(n)=f(n-1)+f(n-2)$

Having very simple sequence $f(n)=f(n-1)+f(n-2)$ and having $n-th$ term given how can we calculate from which first two terms this $n-th$ term came? I know the answer can be not unique so highest ...
3
votes
1answer
175 views

What's the reasoning for this recurrence on $q$-multinomial coefficients?

I'm familiar with the recurrence for binomial coefficients based on Pascal's triangle. However, in general, there is the recurrence for $q$-multinomial coefficients given by $$ ...
3
votes
5answers
521 views

recurrence relation, linear, second order, homogeneous, constant coefficients, generating functions

How to solve this by using the generating functions? What is the possible solution for this? recurrence relation $$ a_n = 5a_{n-1} – 6a_{n-2}, n \ge 2,\text{ given }a_0 = 1, a_1 = 4.$$ Thanks.
2
votes
2answers
2k views

Characteristic equation of a recurrence relation

Yesterday there was a question here based on solving a recurrence relation and then when I tried to google for methods of solving recurrence relations, I found this, which gave different ways of ...
1
vote
0answers
98 views

How to find the recurrence polynomial?

Problem: If $f$ is a polynomial with unknown roots $x_1,-x_1,x_2,-x_2\ldots,x_b,-x_b \quad (b \in \mathbb{N})$ and can be expressed as (known expansion): $$f(x)=\sum_{a=0}^{2b}f_ax^a\quad(b \in ...
2
votes
3answers
132 views

Solve recurrence equations-homework extras

Extras from my homework. The first one should be easier, but still hard enough. 1) $a_{n+3}-(3/2)a_{n+2}-a_{n+1}-(1/4)a_n=0$ 2) $a_{n+3}-3a_{n+2}-3a_{n+1}+a_n=n^2+2^n$
2
votes
2answers
598 views

Recurrence for a lagged Fibonacci sequence

I know how to do the matrix for the standard $f(n) = f(n-1) + f(n-2)$ relationship, but what if it's piecewise? For instance, $f(1)$ through $f(30)$ have some preset values, and then for $f(31)$ ...
1
vote
2answers
120 views

Incorrect inequality after verifying a recurrence solved using the master method

I am trying to solve the recurrence $$T(n) = 4 T \Big( \frac{n}{2} \Big) + n .$$ using the master method and got $\Theta(n^2)$ using the first case theorem: If $f(n) = ...
2
votes
3answers
171 views

Find a closed term for $f(n) = n + 2 f(n-1)$, $f(1)=1$

I cannot help myself, but I don't get the closed term for: $f(n) = n + 2 f(n-1)$, where f(1) = 1. I tried to find the pattern when looking at some iterations, and I think I see the pattern very ...
1
vote
2answers
352 views

Find the asymptotic growth of $t(n)$ satisfying $t(n)=2^nt(n/2)+n$

Find $\Theta$ of $t(n)$ for $$ t(n)=2^nt(n/2)+n .$$ I can't use Master Theorem because of $2^nt$ and althought I am familiar with other methods, I can't solve it. Is there a chance solve it ...
5
votes
1answer
188 views

two-dimensional recurrence

Can someone using only these conditions $$a_{m,k}=a_{m-1,k}+a_{m-1,k-1},m>k$$ $$a_{m,k}=1,m=k$$ $$a_{m,k}=0,m<k$$ prove that $$a_{m,k}=\frac{m!}{k!(m-k)!}$$ here is way to construct Pascal ...
2
votes
4answers
182 views

recursion need a closed form

Is there a closed formula to the problem $f(1)=1, f(2n)=f(n), f(2n+1)=f(2n)+1$. So far i have found a solution for $n$, which is the number of power of $2$'s needed to add up to the number starting ...
3
votes
1answer
64 views

Is there a name for the this kind of recursive formula?

$a_{-i}=0$ for all positive i. We have the recurrence $$ a_n = \sum_{i=1}^\infty b_ia_{n-m_i} $$ Where $m_i>0$ for all $i$.
2
votes
4answers
134 views

Proving an exponential bound for a recursively defined function

I am working on a function that is defined by $$a_1=1, a_2=2, a_3=3, a_n=a_{n-2}+a_{n-3}$$ Here are the first few values: $$\{1,1,2,3,3,5,6,8,11,\ldots\}$$ I am trying to find a good approximation ...
1
vote
2answers
687 views

Recurrence relations - binary substrings

Let $S_n$ be the number of binary strings of length = $n$ which do not contain the sub-string $010$. Find a recurrence relation for $S_n$. edit: I tried for $n=4$. There are two positions in ...
1
vote
2answers
316 views

Number of subsets of $\{1,2, \ldots, n\}$ containing no three consecutive integers: recurrence equation?

I'm thinking about the problem below. I know that I have to find a polynomial formula for that first, and then from that polynomial formula I can find the recurrence relation. I actually attempted ...
1
vote
1answer
438 views

recursive equation for number of white balls

Consider a polyurn scheme of more than two colors. Let us draw a ball from the urn and replace it with another ball of the color we picked from the urn. We assume that $w$ is the number of white balls ...
2
votes
3answers
168 views

Solving $A(x) = 2A(x/2) + x^2$ Using Generating Functions

Suppose I have the recurrence: $$A(x) = 2A(x/2) + x^2$$ with $A(1) = 1$. Is it possible to derive a function using Generating Functions? I know in Generatingfunctionology they shows show to solve ...
1
vote
1answer
97 views

Sequences defined as solutions to equations : $u_{n}=v_{n}^n$

For $n$ a positive integer at least equal to $2$, define the two following functions as follows : $$ \begin{align*} f_{n}(x) & = \pi/4 + \arctan(\sqrt[n]{x})-\arctan(1/x) \text{ for all ...
3
votes
3answers
2k views

I have a problem understanding the proof of Rencontres numbers (Derangements)

I understand the whole concept of Rencontres numbers but I can't understand how to prove this equation $$D_{n,0}=\left[\frac{n!}{e}\right]$$ where $[\cdot]$ denotes the rounding function (i.e., ...
1
vote
3answers
463 views

A Recurrence Relation Problem

In a standard elimination tournament, a player wins $\$100k$ when she/he wins a match in the $k$th round. Develop and solve a recurrence relation for $a_n$, the total amount of money given away in ...
9
votes
3answers
351 views

Solving the recurrence relation $A_n=n!+\sum_{i=1}^n{n\choose i}A_{n-i}$

I am attempting to solve the recurrence relation $A_n=n!+\sum_{i=1}^n{n\choose i}A_{n-i}$ with the initial condition $A_0=1$. By "solving" I mean finding an efficient way of computing $A_n$ for ...
2
votes
3answers
2k views

Recurrence equation $T(n)=3T(\sqrt{n}) +1$

I need to find an exact solution to the following recurrence using substitution (change of variables). $$ T(n) = 3T(\sqrt{n}) + 1, \quad \text{ when } n > 2, $$ and $$ T(2) = 1 .$$ I can't get ...
0
votes
0answers
481 views

Using recurrences to solve $3a^2=2b^2+1$

Is it possible to solve the equation $3a^2=2b^2+1$ for positive, integral $a$ and $b$ using recurrences?I am sure it is, as Arthur Engel in his Problem Solving Strategies has stated that as a method, ...
0
votes
1answer
150 views

recurrence relation only for odd indices maple

I want to define a recurrence relation $a(n)$ which is only defined for odd n. I tried something like: a:= (2*n-1)->a(2n-3)+(2n-2)!+a(2n-5); which apparently doesn't work. How do I define this ...
0
votes
3answers
73 views

What is the $n$-th sequence element for the generating function $\frac{1}{(1-ax)^2}$?

for e.g. for $\frac{1}{(1-ax)} = a^n$ or for $\frac{1}{(1-x)^2} = n+1$ generating function = $\frac{1}{(1-ax)^2}$
1
vote
1answer
291 views

Solving recursion with 2 parameters

How do i solve a recursion like this: $c_{i,j} = c_{i,j-1} + c_{i-1,j}$ with $c_{i,0} = c_{0,j} = 1$ After one step it can be written as: $c_{i,j} = c_{i,j-2} + 2c_{i-1,j-1} + c_{i-2,j-1}$ which ...
4
votes
3answers
2k views

Solving $T(n)= 2T(n/2)+n \lg (n)$

I am trying to solve a recursive function: $$ T(n)= 2 T(n/2)+n \lg(n), \quad n>2,\quad T(2)=2,\quad n = 2^{k}$$ Master theorem didn't work. The result is pointless (if I did it right). Any ...
2
votes
2answers
168 views

Recurrence $A(n,x)=p(x)A(n-1,x-1)+q(x)A(n-1,x)$

What is the general approach to solving this recurrent equation given that $p(x)$ and $q(x)$ are not constant and do not depend on $n$ and $p(x)+q(x) \neq 1$. Please just give me some hints, don't ...
1
vote
1answer
58 views

Prove that $x_{n} = (n^{2}(n+1)^{2})/4$ via complete induction for the sequence $x_{n+1}=x_{n} + (n+1)^3$

The sequence is described by $x_{n+1}=x_{n} + (n+1)^3$. Prove that $x_{n} = (n^{2}(n+1)^{2})/4$ via complete induction. I actually have two questions. I'm a bit lost as to how to start the induction ...
1
vote
1answer
178 views

Recurrence Problem

$$A(n) = A(n/3) + A(n/2) + A(2n/3) + O(n)$$ So I am trying to solve this equation. I let $A(n) = O(n)$. I then solved the equation this way: $$n/3 + n/2 + 2n/3 + kn,$$ which can simplify to $3n/2 + ...
2
votes
3answers
126 views

Problem with generating functions and binary recurrences

I am considering the following recurrence: $a_0 = 1$; $a_1 = 2$ $a_{n} = 2 (a_{n - 1} + a_{n - 2})$ Then I proceeded with the generating function: $F(x) = \displaystyle\sum_{n = 0}^\infty a_n x^n ...
1
vote
1answer
459 views

Recurrence Relation, closed-form (linear, 2nd order, constant coeff, homogeneous)

If I have a recurrence relation, such as $h_n = h_{n-1} + 2h_{n-2}$, is there a rigid method to find a closed formula for $h_n$? As of right now, I just solve for the first few terms $h_0, h_1, h_2, ...
3
votes
1answer
254 views

Non-linear recurrence problem

How to convert $p_n$ to an expression in terms of $n$ if $3p_{n-1}^2 - p_{n-2}=p_{n}$ and $p_0=5, p_1=7$? This is a problem I haven't been able to finish for two days, please help. This question ...
1
vote
1answer
146 views

Question about generating function in an article

Could someone explain what $R(x)$ and constant $c_1,c_2,...,c_k$ are in this article about characteristic polynomial in proof 3? If that someone could rephrase it, because it seems not so clear in ...
2
votes
2answers
460 views

Limit of a recursive sequence

Let $\lambda$$\in$$(0,1)$. For any real $a_0$, $a_1$, define the sequence recursively by $$a_n = (1-\lambda)a_{n-1} + \lambda a_{n-2}$$ Let $\alpha$ = $\lim\limits_{n\rightarrow\infty}a_n$ Express ...
0
votes
1answer
86 views

Can we express $p_n$ in terms of $p_0, p_1$ and $n$?

$p_0=a$, $p_1=b$, $bp_n=p_{n+1}+p_{n-1}$ express $p_n$ in terms of $a,b,n$. Any help would be appreciated, because you guys are splendid.
3
votes
1answer
271 views

Expanding the generating function of the Fibonacci numbers to find a cute formula

$F_0=1$, $F_1=1$, $F_n=F_{n-1}+F_{n-2}$. The generating function is $-\frac{1}{x^2+x-1}$. I have to expand it to prove that $F_n=\sum_k\binom{k}{n-k}$. Could you help me please?
4
votes
1answer
536 views

On the generating function of the Fibonacci numbers

Let's define the Fibonacci numbers as $F_0=1$, $F_1=1$ and $F_n=F_{n-1}+F_{n-2}$. Using this recurrence I was able to calculate the generating function of the Fibonacci numbers to be ...
4
votes
2answers
163 views

Solving a recurrence using substitutions

I have to solve this recurrence using substitutions: $(n+1)(n-2)a_n=n(n^2-n-1)a_{n-1}-(n-1)^3a_{n-2}$ with $a_2=a_3=1$. The only useful substitution that I see is $b_n=(n+1)a_n$, but I don't know ...
0
votes
1answer
794 views

Rearranging a general closed form linear recurrence sequence

I have the following general closed form linear recurrence equation: $$x_n=r^{n-1}a+\left(\frac{r^{n-1}-1}{r-1}\right)d, \qquad (n=1,2,3,...)$$ and the next stage in the text shows the equation ...
3
votes
2answers
229 views

Build recurrence relation from a Combinatorial problem

$a_n$ is the number of sub sets of $A=[{-n,...,-1,1,...,n}]$. The sub sets doesn't contains: Two positive consecutive numbers. Opposite numbers. Note: $0\notin A$ Build ...
0
votes
3answers
233 views

In attempting a closed solution for a recurrence, what am I failing to do?

I'm doing a coursework assignment and find myself rather stuck. I thought I understood back-substitution as a method for solving recurrences but am not finding my working to be getting me anywhere. My ...
0
votes
2answers
93 views

Programmatically Solve Recurrency equations in Closed form?

$$ \begin{cases} V(k)=0 \text{ as } k < 1 \\ V(k+1) -V(k) = \left(\frac{1}{2}\right) \left(V(k) - V(k-1) \right) \text{ as } k \in [1,9] \\ V(k+1) = V(k) \text{ as } k >9 \end{cases} $$ ...
4
votes
1answer
222 views

What types of functions do recurrence relations methods apply to?

I have been working with a function that I defined recursively as $$a(n) = (1-a(n-1)^k)^k$$ where $a(0) = x$ and $k$ is an integer $>1$. So really, $a(n)$ returns a function on $x$ and $k$. I have ...
1
vote
0answers
67 views

Recurrence $A_{n+1}=A_{n}+\mathbf{E}G_n$

This looks like a straightforward recurrence, but I have an impression I made a mistake somewhere. In this equation $G_n$ is a random variable $ G_n=\left\{ \begin{array}{c c} 0 & 1-p_n \\ ...
2
votes
2answers
99 views

What is the asymptotic bound for this recursively defined sequence?

$f(0) = 3$ $f(1) = 3$ $f(n) = f(\lfloor n/2\rfloor)+f(\lfloor n/4\rfloor)+cn$ Intuitively it feels like O(n), meaning somewhat linear with steeper slope than c, but I have forgot enough math to not ...
2
votes
3answers
186 views

Solve $t_{n}=t_{n-1}+t_{n-3}-t_{n-4}$?

I missed the lectures on how to solve this, and it's really kicking my butt. Could you help me out with solving this? Solve the following recurrence exactly. $$ t_n = \begin{cases} n, ...
6
votes
1answer
1k views

Repertoire Method Clarification Required ( Concrete Mathematics )

In the book Concrete Mathematics, chapter 2, section 2.2 -- sums and recurrences, page 26 (2nd edition), the authors talk about the following example: Given the general recurrence $$ R(0) = \alpha ...
9
votes
1answer
378 views

Recurrence for the partition numbers

I'm reading Analytic Combinatorics [PDF] book by Flajolet and Sedgewick, and I can't figure out one of the steps in the derivation of the $P_n$ — number of partitions of size $n$ (or coefficients in ...