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

learn more… | top users | synonyms (2)

2
votes
3answers
804 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
4answers
86 views

Find $x_{n}$ if $x_{1}=a>0$ and $x_{n+1}=\frac{x_{1}+2x_{2}+…+nx_{n}}{n}$

Find $x_{n}$ if $x_{1}=a>0$ and $x_{n+1}=\frac{x_{1}+2x_{2}+...+nx_{n}}{n}$ I have a problem finding sum of $$x_{1}+2x_{2}+...+nx_{n}$$ I don't see the term $x_{2}$ because if $x_{1}=a$ for ...
2
votes
4answers
209 views

Showing a particular recurrence is constant

A sequence, $ ( a_n ) _ { n \in \mathbb{N}} $, is constructed by selecting a value of $ a_0$, and then successively forming the following elements from the equation. $$ a_n = 2- \frac12 a_ { n- 1} ...
2
votes
3answers
50 views

Help with recurrence relation

It 's been a long time since I touched this kind of math , so please help me to solve the relation step by steps : $V_k = (1+i)*V_{k-1}+P$ I know the answer is $V_k = (P/i)*((1+i)^k-1) $ Thanks ...
2
votes
4answers
2k views

Find the limit of a recursive square root sequence.

Find the limit of the sequence $$\left\{\sqrt{2}, \sqrt{2\sqrt{2}}, \sqrt{2\sqrt{2\sqrt{2}}}, \dots\right\}$$ Another way to write this sequence is $$\left\{2^{\frac{1}{2}},\hspace{5 pt} ...
2
votes
3answers
685 views

generalised formula for sum of first $n$ tetranacci numbers

In the case of Fibonacci numbers, the formula for the sum of first $n$ numbers of the series is $f(n+2)-1$, but in the case of tetranacci numbers I am unable to arrive at such formula. Thanks.
2
votes
3answers
6k views

Closed form solution of recurrence relation

I am asked to solve following problem Find a closed-form solution to the following recurrence: $\begin{align} x_0 &= 4,\\ x_1 &= 23,\\ x_n &= 11x_{n−1} − 30x_{n−2} ...
2
votes
3answers
896 views

Converting recursive function to closed form

My professor gave us a puzzle problem that we discussed in class that I could elaborate on if requested. But I interpreted the puzzle and formed a recursive function to model it which is as follows: ...
2
votes
3answers
82 views

solution of a recurrence

How might one solve the recurrence $x_{n+1} + x_n + 2^n = 0$ given the necessary initial conditions ($x_0$)? Possible ideas I have in mind: 1) Generating functions 2) Discrete Laplace ...
2
votes
3answers
81 views

Solve the recursion $a_{n} = n a_{n-1} + (n+1)!$

Define the sequence $\{a_{n}\}$ by $a_{n} = n a_{n-1} + (n+1)!$ for $n \geq 1$ and setting $a_{0} = 1$. Solve this recursion completely. I can solve this rather easily by an induction argument, where ...
2
votes
2answers
242 views

Solving $ T(n) = 1 + 2( T(n-2) + T(n-3) +\cdots+T(0) ) $

I have the following recurrence relation which I have obtained from an algorithm: $$ T(n) = 1 + 2( T(n-2) + T(n-3)+\cdots+T(0) ) $$ with base case $T(0) = 1$ and $ T(1) = 1 $ I would like to be ...
2
votes
2answers
894 views

A recursive formula for $a_n$ = $\int_0^{\pi/2} \sin^{2n}(x)dx$, namely $a_n = \frac{2n-1}{2n} a_{n-1}$

Where does the $\frac{2n-1}{2n}$ come from? I've tried using integration by parts and got $\int \sin^{2n}(x)dx = \frac {\cos^3 x}{3} +\cos x +C$, which doesn't have any connection with ...
2
votes
3answers
50 views

Using recurrence relation: How many n length series using [0,1,2] the sum of each pair is 3 at the most.

Using recurrence relation: How many n length series using [0,1,2] the sum of each pair is 3 at the most. Analyzing the question means that the pair (2,2) where-ever it appear is making the problem. ...
2
votes
5answers
333 views

Deriving Closed Form for a Recursion via Generating Functions

Consider (1) $a_{n+2} = 2a_{n+1} - a_n + 4n3^n$ with $a_0 = a_1 = 1$. Using generating functions and setting $A(x) = \sum a_nx^n$ we obtain $$\begin{align*}&\quad\sum a_{n+2}x^{n+2} = ...
2
votes
3answers
177 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 ...
2
votes
3answers
287 views

Recursion equations: $T(n)=T(\frac{n}{4})+T(\frac{3}{4}n)+1$

What's the simplest way to prove that the solution for this recursion equation: $T(n)=T(\frac{n}{4})+T(\frac{3}{4}n)+1$ , is $T(n)=\theta (n)$? I think that it is $T(n)=\theta (n)$ because it is ...
2
votes
3answers
43 views

Finding an explicit formula for a recursive sequence. [closed]

How to show that the recurrent formula $$A_n=A_{n-1} + A_{n-2} +4.$$ gives a sequence of the form $f(n)=cr^n+cr^n$? The only way we are allowed to solve it, is with the quadratic formula ...
2
votes
2answers
90 views

Does there exist an infinite sequence $p_0,p_1,p_2…$ of prime numbers such that $p_k=4 p_{k-1}\pm 1$

$k \in Z^+$ firstly we know that there exists infinetly many primes of the form $4n+1$ by FTA also we see that if we consider finite primes say to $n$ then the recursive formular can be expressed ...
2
votes
4answers
5k views

how to find nth term in a fibonacci series or sum of a series of fibonacci numbers

A series is given as $1,6,7,13,20,33,.......$ and so on Find the sum of first 52 terms? what i know is The sum of the first n Fibonacci numbers is the [(n + 2)nd Fibonacci number - 1] . So the sum ...
2
votes
1answer
90 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
3answers
774 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
319 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
148 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
57 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
47 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
77 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
284 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
61 views

$n$th derivative of $e^{-x^2}$

I observed that $f^{(n)}(x)= \begin{cases} e^{-x^2} & \text{if $n=0$}\\ -2xe^{-x^2} & \text{if $n=1$}\\ f^{(n-1)}(x)-f^{(n-2)}(x) & \text{otherwise.} \end{cases}$ How to get the closed ...
2
votes
3answers
124 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
184 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
150 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
231 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
143 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
87 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
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
738 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
159 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
195 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
983 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
150 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
717 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
205 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
545 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 ...