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

learn more… | top users | synonyms (2)

0
votes
0answers
12 views

Linear recurrent sequences and matrices.

Let $k$ be a field, let $d$ be an integer greater than $1$, let $(v,x)\in k^d\times k^d$ and let $A\in k^{d\times d}$ be invertible. For all $n\in\mathbb{N}$, let define the following element of ...
0
votes
1answer
46 views

How to evaluate or approximate this kind of recursion: $a(n+1) = m \cdot \exp(-K \cdot a(n) / m)$?

I came up on a recursive definition of a function, given by $$a(n+1) = m \cdot \exp(-K \cdot a(n) / m),\ n \geq 2$$ with $m$ and $K$ being fixed integers ($m$ large). The first terms of the recursion ...
0
votes
0answers
17 views

Finding a general solution of recurrences

I am unsure how to even start the questions :S I need to learn this stuff for the final exam of my subject and its hard to find a tutorial on how to answer this type of question.
0
votes
1answer
18 views

non-homogeneous Recurrence Relation for f(x) = n^2

Im having some trouble with a non-homogeneous Recurrence Relation. My question is: $u_{n} - 5u_{n-1} + 4u_{n-2} = n^2$ My working out so far: $r^{2}-5r+4r = 0$ = (r-1)(r-4) Giving the roots 1 and ...
3
votes
3answers
192 views

Is there a general method for solving this type of recurrence?

Edit: Here is the original problem; it is possible that my recurrence for the stationary distribution $\pi$ is incorrect. Consider a single server queue where customers arrive according to a ...
0
votes
1answer
75 views

recursive generating functions

\begin{align} f(0) & = 1 \\ f(1) & = 1 \\ f(2) & = 2 \\ f(2n) & = f(n)+f(n+1), \;\;\;n\gt1 \\ f(2n+1) & = f(n-1)+f(n), \;\;\;n\ge1 \\ \end{align} I am trying to figure out ...
1
vote
4answers
69 views

Recurrence relation $a_r+6a_{r-1}+9a_{r-2}=3$, then find $a_{20}$

Consider the recurrence relation $a_r+6a_{r-1}+9a_{r-2}=3$, given that $a_0=0, a_1=1$. Let $a_{20}=x\times10^9$, then the value of $x$ is______ . My attempt: $a_r=3-6a_{r-1}-9a_{r-2}$ I ...
2
votes
0answers
87 views

Calculate n-th term of a recursive formula

I have a sequence defined as follows: $a_1 = A$ $a_n = a_{n-1}^2 + B$ $A, B$ are positive integers. I want to design an algorithm, which would calculate $N$-th term of this recurrence modulo $M$ ...
3
votes
5answers
121 views

Prove upper bound for recurrence

I am working on problem set 8 problem 3 from MIT's Fall 2010 OCW class 6.042J. This is covered in chapter 10 which is about recurrences. Here is the problem: $$A_0 = 2$$ $$A_{n+1} = A_n/2 + 1/A_n, ...
1
vote
1answer
86 views

Ternary strings (combinatorics, recurrence)

The questions is: for $A_n$ find all ternary strings of length $n ≥ 0$ that don't include substring $”11”$. Provide answer in form of: a) recurrence relation b) combinatorial expression After that, ...
2
votes
1answer
54 views

Solving $nx_n=(n+2)x_{n-1} + 1$ by the telescoping method

I am trying to solve this recurrence relation from a book "Problem solving through Problems" by Loren c. Larson (5.3.14 (b)) using the telescoping method. $$x_0=0\qquad nx_n=(n+2)x_{n-1} + 1\ (n > ...
0
votes
4answers
75 views

Is this recurrence relation $g_{n+1}=ig_n-g_{n-1}$ is a trivial?

Let $g_1=i$ and $g_2=-1$, where $i=\sqrt{-1}$, and $$g_{n+1}=ig_n-g_{n-1}$$ For $n=1,2,3,4, ...$ then $g_n:={i, -1, -2i, 3, 5i, -8, -13i, 21, ...}$ respectively. Is this recurrence relation is ...
1
vote
0answers
18 views

Difference equations and the characteristic polynomial

The context for this is solving the gambler's ruin problem using linear algebra. I haven't found a good explanation for why the linear combination of the eigenvalues for the matrix representing a ...
0
votes
2answers
52 views

Find and solve a recurrence relation for the number of words of length n from letters A, B, C, and D

Find and solve a recurrence relation for the number of words of length $n$ from letters $A, B, C,$ and $D$ which contain at least one $A$ and the first $A$ comes before the first $B$ (if there are any ...
1
vote
1answer
32 views

Let t(n) be the number of strings of n letters that can be produced by concatenating copies of the string “a”, “bc”, “cb” find t(3) and t(4)

For each integer n>= 1, let $t_n$ be the number of strings of n letters that can be produced by concatenating (running together) copies of the strings "a", "bc", and "cb" For example, $t_1$ = 1("a" ...
0
votes
2answers
35 views

Recursive sequence nth element formula

What is the $n$th element of this sequence: $$S_n = S_{n-1} + (c_1 - S_{n-1})c_2$$ where $c_1$ and $c_2$ are constants and $S_1=0$. Thank you,
2
votes
0answers
37 views

$a(n+1, k) = ka(n,k) + a(n,k-1)$

While working a combinatorial problem, I have encountered the recurrence relation $$a(n+1, k) = ka(n,k) + a(n,k-1)$$ where $a(0,0) = 1$ and $a(0,k)=0$ if $k \ne 0$. Except for the $k$ multiplier, ...
0
votes
1answer
14 views

Inequality in recurrence relation

I'm having a mental block understanding what is probably a simple inequality in a guess and check example for a recurrence relation. Would someone please explain to me how they obtain the inequalities ...
4
votes
2answers
51 views

Show that the sequence $x_n=\Big[\frac32x_{n+1}\Big]$, $x_1=2$ contains an infinite set of odd numbers and an infinite set of even numbers.

I am having a hard time proving this Let $x_n$ be a sequence such that $x_{n+1}=\Big[\frac32x_n\Big]$ for $n\gt1$, where $[x]$ denotes the nearest integer function and $x_1=2$. Show that ...
1
vote
0answers
43 views

How can I solve the recurrence [on hold]

Solve the recurrence $f(n)=f(\frac{3n}{4})+f(n^{1-b})+cn^b$ where b and c are constants and 0 < b < 1.
0
votes
1answer
26 views

Solving differential equations using series

Suppose $v \in \mathbb{R}$ and $$y\left(x\right)=x^v\left(1+\sum^{\infty}_{n=1}a_nx^n\right)$$ where the series converges for any $x \in \left(-r,r\right), r>0$ If $y\left(x\right)$ is a solution ...
1
vote
0answers
15 views

Frobenius Method

We have been given a Hermite equation $ \frac{d^2 y}{dx^2} -2x \frac{dy}{dx}+2ny=0$ We need to use the Frobenius method to solve. So far we have solved the indicial equation and got r = 0,1 and the ...
0
votes
1answer
40 views

Properties of Bessel Functions

I have shown that the Bessel function $$J_n\left(x\right)=\dfrac{x^n}{2^n}\sum^{\infty}_{n=0}\dfrac{\left(-1\right)^kx^{2k}}{2^{2k}k!\left(n+k\right)!}$$ satisfies the property ...
0
votes
1answer
30 views

Find the Bessel Function solution of the differential equation

For positive n, the ordinary differential equation $$y''+\dfrac{1}{x}y'+\left(1-\dfrac{n^2}{x^2}\right)y=0$$ has as a solution the Bessel function of order n, ...
1
vote
1answer
30 views

How to solve master theorem $T(n) = 3T\left(\frac{n}{2}\right) + \frac{n^2}{\log_2 n}$

Im trying to solve this using master theorem $T(n) = 3T\left(\frac{n}{2}\right) + \frac{n^2}{\log_2 n}$ but I dont know how. So far we know that $a=3$, $b=2$, $f(n) = \frac{n^2}{\log_2 n}$. Which ...
7
votes
1answer
83 views

Repeatedly taking mean values of non-empty subsets of a set: $2,\,3,\,5,\,15,\,875,\,…$

Consider the following iterative process. We start with a 2-element set $S_0=\{0,1\}$. At $n^{\text{th}}$ step $(n\ge1)$ we take all non-empty subsets of $S_{n-1}$, then for each subset compute the ...
1
vote
1answer
27 views

Where does this reccurence relation come from?

if$$\alpha_m = \int^{1}_{-1}\cos \pi x (x^2-1)^m dx$$ then how do I get $$\alpha_m = \frac{-1}{\pi^2}(2m(2m-1)\alpha_{m-1} + 4m(m-1)\alpha_{m-2})$$ I have to integrate by parts! But $$\alpha_n = ...
1
vote
0answers
106 views

Are there bounded nonconvergent sequences satisfying this recurrence relation?

In this question, we ask about convergent sequences $(p_n)$ satisfying $p_{i} = 2p_{i+6} - {1 \over 2}p_{i+1} - {1 \over 4}p_{i+3} - {1 \over 8}p_{i+7} - {1 \over 16}p_{i+15} - {1 \over 32}p_{i+31} - ...
0
votes
1answer
29 views

Find a recurrence relation and the Fourier-Legendre Series

Rodrique's Formula for the $n$th Legendre Polynomial is $$P_n\left(x\right)=\dfrac{1}{2^nn!}\dfrac{d^n}{dx^n}\left(\left(x^2-1\right)^n\right)$$ The Fourier-Legendre series of a function f is ...
1
vote
1answer
76 views

Given $x_m=4x_{m-1}-x_{m-2},\ x_1=1,\ x_2=3$

I friend told me that apart from trivial ones, the elements in this sequence never equal powers of 3: $$x_m=4x_{m-1}-x_{m-2},\ x_1=1,\ x_2=3.$$ Could you please help me to prove this?
2
votes
1answer
89 views

Bessel's Differential Equation - textbook queries:

In order to ask this question I must first give some background information as written in my text book: Given Bessel's Differential equation: $$x^2y^{\prime\prime}+xy^{\prime}+(x^2-p^2)y=0$$ ...
1
vote
0answers
16 views

Deducing Skolem-Mahler-Lech theorem from a $p$-adic interpolation result.

Let $p$ be a prime number, let $d$ be an integer greater than $1$ and let $f\in\mathbb{Z}_p[X_1,\cdots,X_d]^d$. I have already proved the following $p$-adic interpolation theorem: Theorem 1. ...
0
votes
3answers
20 views

General and particular solution from recurrence equation

I need to find the General Solution of $S_n = 3S_{n-1}-10$ for n = 1,2,3,4.... then I need to find the particular solution where $S_0 = 15$, then check the particular solution with the original ...
-2
votes
0answers
28 views
5
votes
1answer
51 views

Fibonorial of a fractional or complex argument

Let $F(n)$ denote the $n^{\text{th}}$ Fibonacci number$^{[1]}$$\!^{[2]}$$\!^{[3]}$. The Fibonacci numbers have a natural generalization to an analytic function of a complex argument: ...
-1
votes
1answer
32 views

Need to find the recurrence equation for coloring a 1×n board with no specific sequence aoccure [closed]

Let $a_n$ be the number of ways to to color the square $1 \times n$ board using the colors red, white, and blue, So that specific sequence red-white-blue does not occur. i have 2 cases case 1 if ...
0
votes
2answers
34 views

How to find limit of the sequence

A sequence is defined by recurrence relation $f_{n+1}=\frac{3}{7}f_n+8$ with $\mu_0=-14$, then what is the limit of the sequence? $14$ $-14$ $\frac{-3}{7}$ $\frac{3}{7}$ My attempt: As wiki ...
1
vote
0answers
40 views

asymptotic behavior of functions which are defined recursively

For $x\in[0,1]$, define $f_1(x)=1$ and $$ f_{n+1}(x)=(1-x)^n\left(nx+1\right)+f_n(x)\left(1-(1-x)^{n+1}\right)\;\;\mbox{for}\;\;n=1,2,\dots. $$ I want to study some asymptotic results of $f_n$. For ...
0
votes
2answers
31 views

recurrence relation number of bacteria

Assume that growth in a bacterial population has the following properties: At the beginning of every hour, two new bacteria are formed for each bacteria that lived in the previous hour. During the ...
2
votes
2answers
60 views

Intersection of two recurrences.

I have two sequences obtained by recurrences: $$f(0) = 1, f(1) = 9, f(n+2) = 10f(n+1) - f(n)$$ $$g(0) = 1, g(1) = 7, g(n+2) = 6g(n+1) - g(n)$$ How can I prove that apart from $f(0) = g(0) = 1$, these ...
4
votes
3answers
2k views

Notation for factorial-type pattern with a skip/step of two instead of one?

I came across a peculiar pattern when solving a recurrence relation today: Some sequence $a_n$ looks as such: $a_0 = 1$ $a_2 = \frac{1}{2 \cdot 1}$ $a_4 = \frac{1}{4 \cdot 2 \cdot 1}$ $a_6 = ...
-1
votes
1answer
77 views

Is there a sequence of positive integers such that $a_{n+3}-a_{n+2}=\sqrt{a_{n+1}+a_n}$? [closed]

Can anyone give me a hint on this? Is there a sequence of positive integers such that $(a_{n+3}-a_{n+2})^2=a_{n+1}+a_n$ for all $n$? Or strongly, $a_{n+3}-a_{n+2}=\sqrt{a_{n+1}+a_n}$. If there is, ...
0
votes
1answer
26 views

Particular Solution of Recurrence Equation

Given: $S_{n+2} = 13S_{n+1} + 48S_n$ for $\forall n \in N$ I've found the General Solution which is $S_n = A16^n - B3^n$ I don't quite understand how to find the particular solution where $S_0 = 1$ ...
2
votes
3answers
32 views

General Solution and Particular Solution of Recurrence Equation

I am given: $S_{n+2} = S_{n+1}+S_{n} + {2}$ for $\forall n \in N$ My question is how do I find the general solution of the recurrence equation. And the particular solution where $S_0=1$ and $S_1 = ...
0
votes
1answer
21 views

How do I solve this first order difference equation?

I have the difference equation: $x(n+1) = \beta + x(n)(1-\alpha - \beta)$, where $\alpha, \beta$ are constants, with initial condition $x(0) = 1$. The solution says that the answer is $$x(n) = ...
7
votes
2answers
467 views

Recurrent sequence limit

Let $a_n$ be a sequence defined: $a_1=3; a_{n+1}=a_n^2-2$ We must find the limit: $$\lim_{n\to\infty}\frac{a_n}{a_1a_2...a_{n-1}}$$ My attempt The sequence is increasing and does not have an upper ...
1
vote
2answers
65 views

How can I prove if these are (or not) possible solutions for the following recurrence?

So I'm presented with no initial conditions and the following recurrence relation: $8a_{n+2}+4a_{n+1}-4a_n=0$ I need to determine if these are possible solutions, and in that case, which initial ...
1
vote
1answer
44 views

Master theorem with $f(n) = n\log(\log n)$

I have a question related to algorithm time complexity and master theorem. How to solve this master theorem $T(n) = 2T(n/2) + n\cdot \log(\log(n))$? We have 3 cases: I don't know which one to ...
1
vote
0answers
19 views

Determining the E.G.F from an Umbral Type Recurrence Formula

Suppose I have the recurrence formula $$\left(A+\frac{2}{3}\right)^n+w_3^2\left(A+\frac{1+w_3}{3}\right)^n+w_3\left(A+\frac{1+w_3^2}{3}\right)^n=0; A_0=1, A_1=-\frac{1}{3}$$ where ...
5
votes
1answer
77 views

If $s(1)=1$ and $s(n)=s(n-1)+\text{lcm}[n,s(n-1)]-(-1)^n$ then $\lim\limits_{n\to \infty}\frac{s(n)}{(n+1)!}=\frac{1}{e}$

Define the sequence $(s(n))$ recursively by $s(1)=1$ and, for every $n\ge2$, $$s(n)=s(n-1)+\text{lcm}[n,s(n-1)]-(-1)^n.$$ Prove that $$\lim_{n\to \infty}\frac{s(n)}{(n+1)!}=\frac{1}{e}$$ I ...