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

learn more… | top users | synonyms (2)

2
votes
3answers
768 views

Monotone and Bounded Sequences: Proof

Say $s_1=1$ and $s_{n+1}=\frac{1}{5}(s_n+7)$ for $n\geq 1$. Prove that the sequence is monotone and bounded, then find the limit.
2
votes
3answers
316 views

Closed Form of Recurrence Relation

I have a recurrence relation defined as: $$f(k)=\frac{[f(k-1)]^2}{f(k-2)}$$ Wolfram Alpha shows that the closed form for this relation is: $$ f(k)=\exp{(c_2k+c_1)} $$ I'm not really sure how to go ...
2
votes
2answers
147 views

Does this sequence always go to $(0,0,0,0)$?

Start with a sequence $S =(a, b, c, d)$ of positive integers and find the derived sequence $$S_1 = T(S) = (|a −b|, |b−c|, |c−d|, |d −a|).$$ Does the sequence $S, S_1, S_2 = T(S_1), S_3 = T(S_2), ...
2
votes
3answers
99 views

Another recurrence sequence problem

I'm working on the following problem: Let be the sequence $x_{n}$, $n \geq0$, $x_{0}=1$,$x_{1}=0$ where $x_{n+2}-2x_{n+1}+2x_{n}=0.$ I need to find out the $x_{n}$, and i'm looking for an easy ...
2
votes
4answers
249 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$.
2
votes
3answers
56 views

Is there an analytic expression for this recursive sum? $C_n = \sum _{k=0}^{n-1}C_k C_{n-1-k}$ [closed]

Is there an analytic expression for this recursive sum ? Say , $C_n = ?$ \begin{align*} C_n =& \sum _{k=0}^{n-1}C_k C_{n-1-k} \\ =& C_0C_{n-1} + C_1C_{n-2}+\cdots+C_{n-1}C_0 \end{align*} ...
2
votes
1answer
46 views

Solve the following recurrence relation:

Solve the following recurrence relation: $f(1) = 1$ and for $n \ge 2$, $$f(n) = n^2f(n − 1) + n(n!)^2$$ How would I go about solving this? Would I need to find a substitution $f(n) =\text{ insert ...
2
votes
2answers
74 views

How can I solve this recurrence relation?

Suppose $A_n = n + nA_{n-1}$, How can I figure out an equation for $A_n$ in terms of $n$? Let the base case $A_0 = 0$.
2
votes
3answers
108 views

Solving a recurrence relation of second order

I have a pattern, which goes: $x_n =2(x_{n-1}-x_{n-2})+x_{n-1}$ and this pattern holds for all $n \ge 2$. I also know that $x_0 = 1 \ and \ x_1 = 5.$ $x_2 = 2(x_1-x_0)+x_1$ $\begin{align} x_3 = ...
2
votes
1answer
262 views

Solving the recursion $y_n=2ny_{n-1}$ with Wolfram|Alpha

This is blowing my mind away ... this should be easy stuff! Starting with the recursive formula $y_n=2n*y_{n-1}$ where $y_1=5.$ I'm trying to come up with a formula for the series { 5, 20, 120, 960, ...
2
votes
3answers
120 views

How to tackle a recurrence that contains the sum of all previous elements?

Say I have the following recurrence: $$T(n) = n + T\left(\frac{n}{2}\right) + n + T\left(\frac{n}{4}\right) + n + T\left(\frac{n}{8}\right) + \cdots +n + T\left(\frac{n}{n}\right) $$ where $n = ...
2
votes
4answers
177 views

Recurrence sequence limit

I would like to find the limit of $$ \begin{cases} a_1=\dfrac3{4} ,\, & \\ a_{n+1}=a_{n}\dfrac{n^2+2n}{n^2+2n+1}, & n \ge 1 \end{cases} $$ I tried to use this - $\lim ...
2
votes
4answers
148 views

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+…+T(\frac n {2^k})$

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ while k is some constant and for any $n\leq3$ $\ T(n)=c$ for k=1 ...
2
votes
3answers
224 views

How do you solve a recurrence with a summation function inside

Show that $$t(n) = 1 + \sum_{ j=0}^{n-1} t(j)$$ is the same as $$t(n) = 2^n$$ Initial condition $t(0) = 1$
2
votes
2answers
140 views

Finding Binet's formula using generating functions

$\newcommand{\fib}{\operatorname{fib}}$ I am trying to solve the Fibonacci recurrence using generating functions, but I've run into a bit of a snag. Here's what I've done so far: $$\begin{align} ...
2
votes
3answers
85 views

Solving Recurring Relations

Can you please help, my son has been trying for over two hours now to solve the following: A sequence of terms $\left\{u_n\right\}$ is defined for $n\geq 1$, by the recurrence relation: ...
2
votes
1answer
85 views

Nonlinear difference equation

Maybe this is a trivial question, but how to find the general solution to the following first order difference equation? $$ y_{t+1}=a+\frac{b}{y_{t}} $$ Also, could someone recommend a reference ...
2
votes
1answer
62 views

How to solve $x_{n+1} = \frac{x^2_n + 1}{x_n}$ if $x_0>1$?

How to solve the following recurrence relation, assuming that $x_0 > 1$: $$x_{n+1} = \frac{x^2_n + 1}{x_n}$$ Am I allowed to divide the fraction, that is $x_{n+1} = x_n + \frac{1}{x_n}$?
2
votes
3answers
733 views

Number of sequences with n digits, even number of 1's

ASKED: Let $c_n$ be the number of sequences with $n$ digits from $\{1,2,3,4\} $ with an even number of $1's$. Determine $c_n$ for $n \geq 0$. GIVEN RESULT: $c_{n+1} = 3 \cdot c_n + 1 \cdot ...
2
votes
1answer
77 views

Solving Recurrent Relation

$a_{1}=\dfrac{3}{5}$ , $~$ $a_{n+1}=\sqrt{\dfrac{2a_{n}}{1+a_{n}}}$ $~$ $(n\geq 1)$ Find the closed form of $a_{n}$
2
votes
4answers
157 views

Solving recurrence relation, $a_n=6a_{n-1} - 5a_{n-2} + 1$

I'm trying to solve this recurrence relation: $$ a_n = \begin{cases} 0 & \mbox{for } n = 0 \\ 5 & \mbox{for } n = 1 \\ 6a_{n-1} - 5a_{n-2} + 1 & \mbox{for } n > 1 ...
2
votes
3answers
192 views

Functional equations and generating functions

The problem asks to find the functional equations for the generating functions whose coefficients satisfy $$ a_n = \sum_{i=0}^{n-1} a_i a_{n-1-i}\,\, (n\geq1), a_0 = 1 $$ There's an example that's ...
2
votes
2answers
98 views

Twice a triangle is triangle

The question is to prove that there are infinitely many triangular numbers $T_n$ where $2 \times T_n$ is also a triangular number, and give the first few as an example. My attempt: $$2 \cdot {x(x+1) ...
2
votes
3answers
155 views

Solve the recurrence $y_{n+1} = 2y_n + n$ for $n\ge 0$

So I have been assigned this problem for my discrete math class and am getting nowhere. The book for the class doesn't really have anything on recurrences and the examples given in class are not ...
2
votes
2answers
974 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
149 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
711 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
89 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
542 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
156 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
74 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
83 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
62 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
160 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
156 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
101 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
136 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
129 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
174 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
79 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
112 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
127 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 ...