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

learn more… | top users | synonyms

3
votes
2answers
210 views

Recurrence relation for $a_{n}$ where $6a_{n}$ and $10a_{n}$ are both triangular

According A180926, the elements of the set {$a:\exists m,n|60a=5n^2+5n=3m^2+3m$} satisfy the following recurrence relation: $$a_{n}=\frac{62a_{n-1}+1+\sqrt{(48a_{n-1}+1)(80a_{n-1}+1)}}{2}$$ ...
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)$ ...
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, ...
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 ...
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 ...
2
votes
1answer
338 views

About the positive sequence $a_{n+2} = \sqrt{a_{n+1}} + \sqrt{a_n}$

Given the positive sequence $a_{n+2} = \sqrt{a_{n+1}}+ \sqrt{a_n}$, I want to prove these. 1) $|a_{n+2}| > 1 $ for sufficiently large $n \ge N$. 2) Let $b_{n} = |a_{n} - 4|$. Show that $b_{n+2} ...
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, ...
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, ...
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
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 ...
4
votes
2answers
1k views

Fibonacci, tribonacci and other similar sequences

I know the sequence called the Fibonacci sequence; it's defined like: $\begin{align*} F_0&=0\\ F_1&=1\\ F_2&=F_0+F_1\\ &\vdots\\ Fn&=F_{n-1} + F_{n-2}\end{align*}$ And we ...
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 $$ ...
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 ...
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
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 ...
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 ...
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$.
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 ...
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 ...
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 ...
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 ...
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 ...
6
votes
1answer
471 views

Solving a simple recurrence relation

I have the following recurrence relation: $a_0=1$ $a_{n}=pa_{n+1}+qa_{n-1}$ Where $p+q=1$. This relation arises in analyzing a "gambler's ruin" situation. It is claimed that the general solution ...
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 ...
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
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 ...
4
votes
1answer
105 views

finding hypergeometric solutions for a recurrence relation

I would like to find all the possible hypergeometric solutions for the recurrence relation defined as $$ (n+2)a_{n+2} - 2(4n+5)a_{n+1} + 8(2n+1)a_n = 0.$$ Is there any way to approach this problem in ...
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 + ...
1
vote
1answer
145 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 ...
6
votes
1answer
240 views

What is the asymptotic behavior of a linear recurrence relation (equiv: rational g.f.)?

The question sounds simple: find the roots of the characteristic equation, take the one with the largest absolute value, and find its coefficient. Repeated roots do not substantially complicate ...
2
votes
2answers
443 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.
4
votes
2answers
162 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 ...
3
votes
1answer
255 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
514 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 ...
0
votes
1answer
772 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
223 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
231 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
91 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
216 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 ...
4
votes
3answers
197 views

If $f(1) = 2$ and $f(n) = n \cdot f(n-1)$ then $f(n) \gt 2^n$ for all $n \gt 2$

I'm having a little difficulty in proving what are probably simple induction proofs. Here is the question. Define function $f(n)$ as follows. $f(1) = 2$ and $f(n) = n\cdot f(n-1)$ when $n > 1$. ...