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

learn more… | top users | synonyms

0
votes
2answers
137 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
512 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
516 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
3answers
398 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
1answer
205 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 ...
27
votes
2answers
534 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
187 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 ...
2
votes
1answer
90 views

Showing two recurrences to be identical

I am trying to prove Cayley's formula for number of labelled trees on n vertices using multinomial coefficients. The multinomial coefficient satisfies the recurrence: $\tbinom{n}{r_1,\cdots ...
2
votes
0answers
235 views

Bell-like recurrence

Let $$A(n)=\sum_{k=0}^{n-1}\binom{n}{k}A(k)+n!,\quad A(0)=1$$ $$B(n)=\sum_{k=0}^{n-1}\binom{n}{k}B(k)-n!-n!\sum_{k=1}^{n}\frac{1}{k!},\quad B(0)=-1.$$ I'm interested in computing $S(n)=A(n)+B(n)$ ...
3
votes
2answers
240 views

Summation of a recurrence relation? [duplicate]

Possible Duplicate: Formula for the summation of this sequence? $$a(2n)=a(n)+a(n+1)$$ $$a(2n+1)=2a(n+1)$$ $$n>1$$ Outputs $1, 2, 4, 6, 10, 12, 16, 20, 22$ etc, but I am trying to find a ...
3
votes
2answers
307 views

Particular solution of recurrence equations

How do we solve recurrence equations of the form: $$ax_{n+1}+bx_n+cx_{n-1}=dn^p+e\;,$$ where $a,b,c,d,e$ are constants and $p\in \mathbb Z$? Perhaps we could first solve the homogeneous equation ...
11
votes
2answers
287 views

Generalized Fibonacci Sequence Question

The Fibonacci Sequence is defined as the recurrence $a(n)=a_{n-1}+a_{n-2}$ where $a(0)=0$ and $a(1)=1$. Today, I was bored so I considered the sequence $a(n)=\sqrt{a_{n-1}}+\sqrt{a_{n-2}}$. Ten ...
1
vote
0answers
105 views

Find $G(n)$ with $n \geq 1$

Let $G(1) = 0, \ G(2) = 1$, $G(2n+1) = 2 + G(n) + G(n+1)$ and $G(2n) = 1 + G(n), \ \ n \geq 1$ Find $G(n) $ P.S: This is little problem in my problem. I tried to solve by using generating function, ...
7
votes
8answers
801 views

Need help deriving recurrence relation for even-valued Fibonacci numbers.

That would be every third Fibonacci number, e.g. $0, 2, 8, 34, 144, 610, 2584, 10946,...$ Empirically one can check that: $a(n) = 4a(n-1) + a(n-2)$ where $a(-1) = 2, a(0) = 0$. If $f(n)$ is ...
2
votes
3answers
265 views

Formula for the summation of this sequence?

$$a(2n)=a(n)+a(n+1), a(2n+1)=2a(n+1),\mbox{ if }n>1$$ Outputs $1, 2, 4, 6, 10, 12, 16, 20, 22,$ etc., but I am trying to find a formula that finds the summation of these terms. For instance, ...
2
votes
1answer
193 views

Solving a recurrence inequality

I am not sure if "recurrence inequality" is the correct term or whether it is possible to actually find an answer to this problem but anyways. Let $n$ be a fixed natural number. Let $R(x,y)$ be a ...
1
vote
2answers
535 views

Recurrence relations and Generating functions - how to find the initial conditions?

Best to ask by example. Given the recurrence relation $a_{n}=a_{n-1}+a_{n-2}$, and some given initial conditions, we can find a similar relation for the generating function for the sequence, ...
1
vote
4answers
253 views

Generalized Fibonacci sequences

Why Fibonacci sequence start at $0$, Tribonacci sequence with $0,0$, Tetranacci with $0,0,0$, etc. [ref OEIS] Has any good reasons for that? These sequences arise in generalization of Pascal Triangle ...
1
vote
1answer
100 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
165 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
4answers
485 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
1k 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
93 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
568 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
117 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
168 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
336 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
169 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
179 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
63 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
131 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
619 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
270 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
426 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
167 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 ...
2
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
421 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
341 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
480 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
146 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
257 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 ...
3
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
163 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
176 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
115 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 ...