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

learn more… | top users | synonyms (2)

3
votes
0answers
109 views

Perrin numbers in terms of the generalized hypergeometric function?

Given the roots of $x^3=x^2+1$, we have sequence A001609, $M(n) = x_1^n+x_2^n+x_3^n = \,_3F_2\left(\frac{-n}{3}, \frac{1-n}{3}, \frac{2-n}{3};\; \frac{1-n}{2}, \frac{2-n}{2};\; ...
3
votes
2answers
103 views

recursive relation with sequences

I am not sure how to properly do this question but I am told that the solution I came up with is wrong and I dont see how...I basically used algebra and plugging of variables and rearranging ...
3
votes
0answers
195 views

Solve recurrence relation $a(n)=2\cdot a(n-1)+5\cdot a(n-2)+6\cdot a(n-3)$ and the associated cubic [duplicate]

I am trying to solve following : $$a(n)=2\cdot a(n-1)+5\cdot a(n-2)+6\cdot a(n-3)$$ with the initial conditions given by $a(0)=3,a(1)=2,a(2)=14$. So first of all, I want to mark that there exists ...
3
votes
0answers
62 views

Properties preserved under the “reversal” of a recurrence equation

Consider the recurrence equation $u_n = f(u_{n-1},\ldots, u_{n-k})\;,$ defined for $n=0,1,2\ldots$. If this is a linear recurrence and the coefficient function on $u_{n-k}$ is nonzero in ...
2
votes
5answers
697 views

Explanation of recursive function

Given is a function $f(n)$ with: $f(0) = 0$ $f(1) = 1$ $f(n) = 3f(n-1) + 2f(n-2)$ $\forall n≥2$ I was wondering if there's also a non-recursive way to describe the same function. WolframAlpha tells ...
2
votes
5answers
197 views

Solving the recurrence relation [closed]

I'm interested in learning how can we solve this linear non-homogeneous recurrence relation? $$a_z = 2a_{n-1} - 1a{n-2} + (s^2 + 1)$$
2
votes
6answers
277 views

I know that, $S_{2n}+4S_{n}=n(2n+1)^2$. Is there a way to find $S_{2n}$ or $S_{n}$ by some mathematical process with just this one expression?

$S_{2n}+4S_{n}=n(2n+1)^2$, where $S_{2n}$ is the Sum of the squares of the first $2n$ natural numbers, $S_{n}$ is the Sum of the squares of the first $n$ natural numbers. when, $n=2$ ...
2
votes
3answers
827 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 ...
2
votes
2answers
533 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 ...
2
votes
5answers
5k views

Solve the recurrence $T(n) = 2T(n-1) + n$

Solve the recurrence $T(n) = 2T(n-1) + n$ where $T(1) = 1$ and $n\ge 2$. The final answer is $2^{n+1}-n-2$ Can anyone arrive at the solution?
2
votes
4answers
153 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
305 views

Coloring dots in a circle with no two consecutive dots being the same color

I ran into this question, it is not homework. :) I have a simple circle with $n$ dots, $n\geqslant 3$. the dots are numbered from $1\ldots n$. Each dot needs to be coloured red, blue or green. No ...
2
votes
4answers
344 views

can one derive the $n^{th}$ term for the series, $u_{n+1}=2u_{n}+1$,$u_{0}=0$, $n$ is a non-negative integer

derive the $n^{th}$ term for the series $0,1,3,7,15,31,63,127,255,\ldots$ observation gives, $t_{n}=2^n-1$, where $n$ is a non-negative integer $t_{0}=0$
2
votes
3answers
190 views

Solve $t_{n}=t_{n-1}+t_{n-3}-t_{n-4}$?

I missed the lectures on how to solve this, and it's really kicking my butt. Could you help me out with solving this? Solve the following recurrence exactly. $$ t_n = \begin{cases} n, ...
2
votes
4answers
2k views

$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer

$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer, need help, I dont know how to solve it?
2
votes
4answers
814 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
88 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
211 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
688 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
900 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
245 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
3answers
322 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
909 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
346 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
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
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
166 views

partitions and their generating functions and Partitions of n

A partition of an integer, n, is one way of writing n as the sum of positive integers where the order of the addends (terms being added) does not matter. p(n, k) = number of partitions of n with k ...
2
votes
3answers
63 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
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
1answer
92 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
790 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
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
199 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
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
58 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
2answers
50 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
82 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
293 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
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
187 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
3answers
232 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$