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

learn more… | top users | synonyms (2)

2
votes
2answers
956 views

Proving convergence of a recursively defined sequence

Using a computer it is easy to see that the sequences defined by letting $a_1=1$, $a_2=m$, and $$a_n=\frac{2a_{n-1}a_{n-2}}{a_{n-1}+a_{n-2}}$$ converges to $\frac{3m}{m+2}$. I would very much like to ...
2
votes
3answers
147 views

recurrence solution to gambler's ruin

From DeGroot 2.4.2, let $a_i$ be the conditional probability that the gambler wins all $k$ given gambler is at $i$. $a_i = pa_{i+1} + (1 - p)a_{i-1} $ It's not clear from the text what steps are ...
2
votes
2answers
700 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)$ ...
2
votes
3answers
202 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
88 views

how many times will a function print to the console?

I have the following snippet: public Foo(int n) { for (int i=0; i<n; i++) { new Foo(i) } console.writeln("?") } For a given $n$, how ...
2
votes
2answers
539 views

Analysis of algorithms and recurrence relations

Suppose that the function of the time of execution of some recursive algorithm is given by a recurrence relation of order $n$. Let $$p(x)=0,$$ with $p(x)$ a polynomial of degree $n$, the corresponding ...
2
votes
1answer
155 views

Basic Recursion

Im trying to write recursive formulas for sequences but it seems like there are different techniques depending on what type of sequence I'm dealing with. for example I want to the sequence: $1 + ...
2
votes
2answers
69 views

How to find a function that is the upper bound of this sum?

The Problem Consider the recurrence $ T(n) = \begin{cases} c & \text{if $n$ is 1} \\ T(\lfloor(n/2)\rfloor) + T(\lfloor(n/4)\rfloor) + 4n, & \text{if $n$ is > 1} \end{cases}$ A. Express ...
2
votes
3answers
90 views

Proving the infinite sum of $1/2^i$ without induction

Prove $$\sum_{i=1}^n \frac{i}{2^i} = 2-\frac{n+2}{2^n} $$ Pretty trivial to do with induction, but as a practice problem for solving recurrences we have to do this only by repeating $\sum_{i=1}^n ...
2
votes
2answers
78 views

Proving an expression is perfect square

I have this expression I got in one larger exercise: $$\frac{(2+\sqrt3)^{2n+1}+(2-\sqrt3)^{2n+1}-4}{6}\frac{(2+\sqrt3)^{2(n+1)+1}+(2-\sqrt3)^{2(n+1)+1}-4}{6}+1$$ and i need to prove it is perfect ...
2
votes
3answers
54 views

Prove that {$r_n$} satisfies $r_n = 7r_{n-1} - 10r_{n-2}, n \geq 2$

Problem: For the sequence $r$ defined by $$r_n = 3 \cdot 2^n - 4 \cdot 5^n, \ \ \ n \geq 0$$ Prove that {$r_n$} satisfies $$r_n = 7r_{n-1} - 10r_{n-2}, \ \ \ n \geq 2$$ Can this problem be ...
2
votes
2answers
59 views

Proving $\lim _{n\to \infty }a_{n+1}=\lim _{n\to \infty }b_{n+1}$ where $a_{n+1}=\frac{a_n+b_n}{2}\:$, $b_{n+1}=\sqrt{a_n\cdot \:b_n}$

$a_1,\:b_1>0$ $a_{n+1}=\frac{a_n+b_n}{2},\:b_{n+1}=\sqrt{a_n\cdot b_n}$ The question asks to prove that: $\lim _{n\to \infty }\left(a_n\right)=\lim \:_{n\to \:\infty \:}\left(b_n\right)$. ...
2
votes
4answers
151 views

Prove sequence is Cauchy.

Prove the sequence $\{a_i\}$ defined by $a_1=1 \text{ and } a_{i+1} = 1 + \frac{1}{a_i}$ is Cauchy. And prove it converges to $\sqrt{2}$. I want to show $\lim\limits_{n\to\infty}(a_{i+1}-a_i)=0$ for ...
2
votes
3answers
154 views

Recurrence relation problem

If $a$ is a sequence defined recursively by $a_{n+1} = \frac{a_n-1}{a_n+1}$ and $a_1=1389$ then can you find what $a_{2000}$ and $a_{2001}$ are? it would be really appreciated if you could give me ...
2
votes
1answer
99 views

General formula of Fibonacci look alike series

I'm trying to discover the general formula of a series defined with recursion: $$ a_1 = 2, a_2 = 3, a_3 = 4 $$ and $$ a_n = a_{n-1} + a_{n-3} $$ It looks like Fibonacci, but the starting points are ...
2
votes
2answers
100 views

How to solve the recurrence $T(n) = T(n-1) +\sqrt{n}$?

While solving the recurrence of the title I come to the series $$T(n) = \sqrt1 + \sqrt2 + \sqrt{3} + \cdots + \sqrt n.$$ Please somebody help me how to solve this.
2
votes
3answers
131 views

Help with a proof that sequence of rational numbers $ a_n = \frac {a_{n-1} + \frac {2}{a_{n-1}}}{2}$ converges to an irrational, $\sqrt2$

I know that there are sequences of rational numbers with irrational limits. One in particular I've seen is $$ a_n = \frac {a_{n-1} + \frac {2}{a_{n-1}}}{2}$$ with $a_0 =1$, This is clearly rational ...
2
votes
2answers
79 views

Zeroes of polynomial

$$c_1,c_2 \text{ are polynomial's }g(x)=x^2+ax+b \text{ roots } \Leftrightarrow \begin{cases} g(c_1)=c_1^2+ac_1+b=0 \\ g(c_2)=c_2^2+ac_2+b=0 \end{cases}$$ Prove that for every polynomial with integer ...
2
votes
3answers
127 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 ...
2
votes
1answer
88 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
3answers
168 views

Solving recurrence relation with generating functions - Nearly got the answer

I'm trying to solve the following recurrence relation (Find closed formula) using generating functions: $f(n)=10f(n-1)-25f(n-2)$, $f(0)=0$, $f(1)=1$ I'm having a small difficulty at the end and can ...
2
votes
2answers
78 views

If $a_{n+1} = u a_n+v a_{n-1}$, what recurrence does $a_{n+1}a_n$ satisfy?

If $a_{n+1} = u a_n+v a_{n-1}$ , what recurrence does $a_{n+1}a_n$ satisfy? You can assume that $u^2+4v > 0$. A starter question, which I have done some work on: If $a_{n+1} = 3 a_n - a_{n-1}$ , ...
2
votes
1answer
149 views

Recurrence relation in complex domain

I am bumping in the following problem : the expansion of $$x^{i/k} \operatorname{LerchPhi}[x,1,i/k]$$ leads, for each value of i, to a linear combination of k terms, each of them writing $$a(j) ...
2
votes
3answers
110 views

Finding a general solution of $A_n$

Find the general solution to $ A_{n+1} + 4A_n = n $ I am unsure how to even start the question :S
2
votes
3answers
77 views

generating functions, can't seem to get the correct answers.

So, I've been having some issues with generating functions and counting problems. An example problem is: $$ a_n = a_{n-1} + 9a_{n-2} - 9a_{n-3} \;\;\; (n \geq 3)$$ Where $a_0 = 0, a_1 = 1, a_2 = 2$ ...
2
votes
1answer
126 views

Show that Fermat number $F_n$ and its index $n$ are coprime.

I want to show that $\gcd(F_n,n)=1$, where $F_n=2^{2^n}+1$. How to prove this? I can show that that $\gcd(F_n, F_m)=1$ for any natural $n$ and $m$, and that $F_{n+1}=(F_n)^2-2F_n+2=F_0\dots ...
2
votes
3answers
144 views

Mathematical induction proof; $g_k=3g_{k-1} - 2g_{k-2}$

Can someone help me with this problem? I'm having a hard time proving this. It's been a long time since I have done mathematical proofs. Suppose that $g_1,\ g_2,\ g_3,\ \ldots$ is a sequence of ...
2
votes
3answers
174 views

Corresponding numerator of the fraction

I am stuck at this question cant think of how to resolve this, sorry I did try to do working but can't think of any right solution. The question is If the denominator is $9900$, then what is the ...
2
votes
4answers
2k 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
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 ...
2
votes
1answer
419 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 ...
2
votes
2answers
121 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
1answer
357 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} ...
2
votes
1answer
168 views
+50

Result of a $2D$ random walk with position dependent probabilities

I was just wondering about $2D$ random walks when I got the idea of a position dependent $2D$ random walk: A man is initially at $(x,y)$ and can move in a line parallel to the X and Y-axis only. ...
2
votes
1answer
32 views

Tower of Hanoi variation from Concrete Mathematics - possible arrangements

From Concrete Mathematics, there is a problem that describes a variation of the Towers of Hanoi, where the disks can not move directly from peg $A$ to peg $B$, but must go through a middle peg. ...
2
votes
5answers
136 views

How to give a good guess to the recurrence relation problem [duplicate]

I have been trying to solve the following recurrence relation $$T(n)=2T(\frac{n}{2}) + nlgn$$ by using substitution method. I started to compute $T(1)$ ,$T(4)$,$T(8)$,$T(16)$ to guess a solution as ...
2
votes
3answers
59 views

Proof by induction that $f(n) = 1-2^{2^n}$, where $f(0) = 3$ and $f(n) = 2 f(n-1) - (f(n-1))^2$

I am doing a textbook question which state that a function $f:\mathbb{N}\to\mathbb{Z}$ is a recursively defined as shown bellow $f(0) =3$, $f(n) = 2\cdot f(n-1) -(f(n-1))^2 $ if $n\ge1$. Prove that ...
2
votes
3answers
71 views

Why do we set $u_n=r^n$ to solve recurrence relations?

This is something I have never found a convincing answer to; maybe I haven't looked in the right places. When solving a linear difference equation we usually put $u_n=r^n$, solve the resulting ...
2
votes
2answers
54 views

Help with a recurrence relation

I have been battling with the following: $$T\left(n\right)=3T\left(\frac{n}{2}\right)+n\log(n)$$ I have tried expanding it but the term $n\log(n)$ gets very messy. What is the approach for solving ...
2
votes
3answers
62 views

Why, intuitively, does the solution to a general linear recurrence relation make sense?

I reasoned through the solution to a differential equation, and $e^{\alpha x}$, for better or worse, seems to make sense. Each derivative sending the function to itself seems to suggest $e^{\alpha ...
2
votes
1answer
108 views

How can I make this recurrent equation non-recurrent?

I have a recurrent equation that defines a sequence $a_k$ from a sequence $b_k$: $$a_k = b_k - \sum^\infty_{i=k+1}a_i$$ How can I write this equation without mentioning $a_k$ on the right side?
2
votes
3answers
161 views

Fibonacci polynomials and factorization redux

I recently asked a question about factorizing a certain expression involving Fibonacci and Lucas polynomials. That question had a very simple and nice answer, but now I've come across another similar ...
2
votes
2answers
422 views

Finding the recurrence relation for number of ways to deposit n dollars

Question: A vending machine dispensing books of stamps accepts only one dollar coins, 1 dollar bills and 5 dollar bills. a) Find a recurrence relation for the number of ways to deposit n dollars in ...
2
votes
2answers
45 views

Maximum of a function from integers to integers

Suppose $f$ is a function form positive integers to positive integers satisfying $f(1)=1$, $f(2n)=f(n)$, and $f(2n+1)=f(2n)+1$ for all positive integers $n$. Job: Find the maximum of $f(n)$ when $n$ ...
2
votes
2answers
88 views

Explicit formula for recurrence

I know how to get explicit formula for simple recurrence $a_n = m_1a_{n-1} + m_2a_{n-2}\dots$ for $m_{1,2\dots}$ being constant numbers. I'm wondering how to get explicit formula for recurrence like ...
2
votes
1answer
44 views

Solving the recurrence $x_n = \frac{\sum_{i=0}^{n-1} x_i}{2n}$

In my answer over at cstheory.stackexchange.com I set variables according to the recurrence $$x_0=1, x_n = \frac{\sum_{i=0}^{n-1} x_i}{2n}$$ Wolfram Alpha tells me that apparently the solution to this ...
2
votes
1answer
74 views

recurrence relation

It was some time ago I studied recurrence relations and I came across this one that I cannot solve: $a_{n+3}=-3a_{n+2}+4a_{n}$ with $a_{0}=2$ and $a_{1}=-5$ Ansatz: $a_{n}=r^{0}$ then I get ...
2
votes
2answers
101 views

Find $a_{2012}-3a_{2010}/3 a_{2011}$ where the sequence $a_n$ is determined by roots of a quadratic equation

If $\alpha$ and $\beta$ are the roots of $x^2-9x-3=0$, $a_n=\alpha^n-\beta^n$ and $b_n=\alpha^n+\beta^n$, then find the value of $\dfrac{a_{2012}-3a_{2010}}{3 a_{2011}}$ and ...
2
votes
1answer
101 views

Strange square brackets in recurrence equation

I have the following recurrence given: $$a_{0}=1$$ $$a_{1}=1$$ $$a_{n}=3a_{n-2}+3a_{n-1}$$ Why is that equal to something like this?: $$a_{n}=3a_{n-2}+3a_{n-1}-2[n=1]+[n=0 ]$$ What are those ...
2
votes
2answers
458 views

Nested roots sequence, how to prove it's monotone and bounded?

Let $a\ge1$ and define the sequence $(x_n)$ recursively by: $$x_1 = \sqrt{a}$$ $$x_{n+1}= \sqrt{a+x_n}$$ Here's what I did: Plugging in some values makes it seem as if the sequence is increasing. I ...