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

learn more… | top users | synonyms (2)

10
votes
0answers
187 views

Recurrence relations with multiple roots of auxiliary equation

Suppose we have a homogeneous linear recurrence relation of the form $$u_{n+r}+a_1u_{n+r-1}+\dots +a_ru_n=0$$ The auxiliary equation is then $$f(x)=x^r+a_1x^{r-1}+\dots +a_r=0$$ It is well known that ...
10
votes
0answers
270 views

Coefficients in expansion of $(\sqrt[3]{2} - 1)^m$

In trying to solve $a^3 - 2b^3 = 1$ over the integers I came across the need to answer the question: when does $(1+ \sqrt[3]{2} + \sqrt[3]{2}^2)^n$ have no $\sqrt[3]{2}^2$ term in it's expansion (in ...
9
votes
0answers
83 views

How to Find the Recurrence Formula for $\int \frac{dx} {(1+\sin x)^n}$?

$$\int \frac{dx} {(1+\sin x)^n}$$ I know that I should use the following step: $$\int\frac{\sin^2(x)\, dx}{(1+\sin x)^n} +\int\frac{\cos^2(x)\, dx} {(1+\sin x)^n} $$ but here I get stuck. I do ...
9
votes
0answers
137 views

Is this a recurrence for the characteristic sequence of composite numbers?

The characteristic sequence of composite numbers is equal to 1 if $n$ is not a prime number and equal to 0 if $n$ is a prime number, starting: $$1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1,...$$ where the ...
8
votes
0answers
81 views

On the convergence of a more complex iterated radical

After exploring Ramanujan's famed $$3=\sqrt{1+2\sqrt{1+3\sqrt{1+\cdots}}} $$ and $$4=\sqrt{6+2\sqrt{7+3\sqrt{8+\cdots}}},$$ both of which can be expressed more generally by $$x+n+a=\sqrt{ax+(n+a)^2+x\...
7
votes
0answers
245 views

Is there a way to write this recurrence relation in faster-to-program manner?

I have the following recurrence relation for some coefficients $$b_{n+2} = \frac{1}{(n+3)(n+2)P_0} \sum_{k=1}^n (n-k+2) (n-k+1) b_k b_{n-k+2}, \quad n>1$$ with $b_1$ to $b_3$ and $P_0$ being the ...
7
votes
0answers
43 views

Bounds (and range) of a nonlinear difference equation

I'm interested in the following set of nonlinear difference equations: $$x_{n+1} = \frac{c + x_n}{x_{n-1}},\; x_1 = x_0 = 1 \qquad \textrm{for } c > 0$$ For $c=1$ the sequence is periodic with ...
7
votes
0answers
65 views

Asymptotic value of card drawing game

A deck consisting of $r_0$ red cards and $b_0$ black cards is randomly shuffled. The host turns up the cards one at a time; if it is red, you get $\$1$; otherwise you pay the host $\$1$ (and you're ...
7
votes
0answers
131 views

An Impossible Sequence of Prime Powers

Let $x_1,x_2,\ldots$ be a sequence of positive integers that satisfies the recurrence relation $$x_{n+1}=2x_n(x_n-1)+1$$ for all positive integers $n$. It seems impossible that every term in this ...
7
votes
0answers
120 views

Minimizing beginning terms of a Fibonacci-like sequence

For $ a, b \in \mathbb{Z}^+ $ such that $ a = b $ or $ 2a < b $, let $ f_{a, b} : \mathbb{Z}^+ \to \mathbb{Z}^+ $ be a sequence that satisfies the following three criteria: $$ f(1) = a, \\ f(2) = ...
7
votes
0answers
71 views

Finding a recurrence relation for a sequence not containing $0$ in the digits. Also showing $\sum\limits_{k=1}^n \dfrac{1}{a_k} < 90$

Let $1,2,3,4,5,6,7,8,9,11,12,\ldots$ be the sequence of all positive integers which do not contain the digit zero. Write $\{a_n\}$ for this sequence. By comparing with a geometric series, show that $\...
7
votes
0answers
179 views

General overview about Recursion (free online texts)

I'm looking for free online texts about recursion. What I'm looking for formal definitions* of "all" (most of) the different types of recursion and from different points of views like Category ...
7
votes
0answers
108 views

Properties of a continued fraction convolution operation

Usually the partial numerators of a continued fraction are all 1s. Has anyone considered the operation where you convolve 1 continued fraction with another, in other words, make a new continued ...
6
votes
0answers
283 views

Sum of infinite series defined recursively

Suppose $s$, $t$, and $\delta$ are constants satisfying $0<s<t<1$ and $\delta>1$. An infinite sequence $\{y_k\}_{k=1}^{\infty}$ defined as follows: The initial term, $y_1$, is the ...
6
votes
0answers
80 views

Right way to solve this reccurence relation?

I am not that good in mathematics , I have solved many simple relations. But I am not be able to solve the following. This is not a homework. I found it during analysis of a program. $T(n)=2T(n-1)+\...
6
votes
0answers
758 views

Asymptotics for the expected length of the longest streak of heads.

As Introduction to Algorithms (CLRS) describes, the problem is Suppose you flip a fair coin $n$ times. What is the longest streak of consecutive heads that you expect to see? The book claims ...
5
votes
0answers
234 views

number of potential couples

A potential couple is a pair of a man and a woman that like each other (assume that 'like' is a symmetric relation). Given a group of $M$ men and $W$ women, I want to know how many different ...
5
votes
0answers
205 views

The simplest delay differential equation

I am trying to understand a bit about solutions of delay differential equations, so I tried analyzing one of the most simple ones: $$u'(t)=-\beta u(t-1), \text{and for } t\in [-1,0), u(t)=\phi(t), \...
4
votes
0answers
61 views

Finite sum with three binomial coefficients

I need to find a closed form expression, if there is one, of the following sum: $$\sum_{j=0}^m{n+1-k\choose j}{k-1\choose m-j}{A+2-k+m-j\choose m-j+2}$$ where all parameters are integers, $~1\leq k\...
4
votes
0answers
187 views

Has this difference equation :$x_{n+1}=Ax^2_{n}-Bx^2_{n-1}$ been studied before?

I posted this problem before in MO but only I would like to know if this difference equation :$$x_{n+1}=Ax^2_{n}-Bx^2_{n-1}$$ where $A(\theta)= \cos(\theta)$ and $B(\theta) =\sin(\theta)$ are ...
4
votes
0answers
79 views

About the existence of a regular solution in a chaotic system

Show that for some choice of $x_1\in\mathbb{R}$, the sequence given by: $$ x_{n+1} = n-3^{x_n} $$ satisfies: $$ \lim_{n\to +\infty} x_n= +\infty. $$ I was able to prove the statement by showing ...
4
votes
0answers
290 views

Series expansion for $x_n=x_{n-1}+\log \left(x_{n-1}\right)$

$x_0=2,\ x_n=x_{n-1}+\log \left(x_{n-1}\right)\quad$ has a series expansion about $1.$ Since $x_0=2,$ $(x_0-1)^k=1,$ so the recurrence can be written, up to the first $5$ terms as \begin{align} 1+\...
4
votes
0answers
102 views

What is the explicit formula (solution) to this recursively defined binary matrix?

My question concerns the following binary matrix (call it matrix $A$). Or rather the entire family of such matrices, for some number of columns $n$ and rows $2^n$. The ellipses indicate that the ...
4
votes
0answers
52 views

Solving system of nonlinear difference equations

This is perhaps a trivial question (I’m an economist), but as a non-matematician that might elude me. I have a (two variable) system of nonlinear difference equations (similar to Riccati type ...
4
votes
0answers
179 views

How to solve a non-homogeneous second-order linear difference equation with both a forward and a backward difference?

Quite a long title for this: I'm looking for the general solution of the following difference equation: $$ax_{t+1} -bx_t + x_{t-1} = c + u_t$$ where $a,b,c$ are real constants and $u_t$ is a bounded ...
4
votes
0answers
63 views

Transform recurrence relation

Is it possible to transform following recurrence relation $a_n=4a_{n-2}-a_{n-4}$, $a_0=1$, $a_1=0$, $a_2=3$, $a_3=0$ so that it will have nonnegative coefficients? Number of terms, of course, can be ...
4
votes
0answers
68 views

Conditions of a Monotonic Process?

$f$ is the output of a discrete time process described by $f(k)=\sum_{i=1}^{k-1}w_{ki}f(i)$ where $f(1)\geq0$ is a known initial condition and $w_{ki}\geq0$ are weights of previous states on the ...
4
votes
0answers
100 views

if $(n+1)c_{n}=nc_{n-1}+2nd_{n-1},d_{n}=2c_{n-1}+d_{n-1}$How prove $c_{n},d_{n}$ are integers

let sequences $c_{n},d_{n}$ such $$c_{0}=0,d_{0}=1$$ and for $n\ge 1$,have $$c_{n}=\dfrac{n}{n+1}c_{n-1}+\dfrac{2n}{n+1}d_{n-1}$$ $$d_{n}=2c_{n-1}+d_{n-1}$$ show that $c_{n},d_{n}$ are integers. my ...
4
votes
0answers
121 views

What is this bifurcation?

I have a discrete dynamical System $x_{n+1}=f(x_{n},x_{n-1},x_{n-2},x_{n-3},x_{n-4},\lambda)$ with a paramteter $\lambda>0$, and where all $x_{n}$s are in [0,1]. $f$ is actually a larger ...
4
votes
0answers
134 views

Lower Bound on fibonacci-like reccurence relation

Given the following recurrence: $T(n) := T(n-k) + T(n-1),\ n,k \in N$ $T(l) := 1,\ l \in \{0,...,k-1\}$ I need to find a lower bound for $T(n)$. (For $k = 2$, the recurrence is equal to the ...
4
votes
0answers
180 views

A functional recursion problem..do you have any idea?

I have a problem which is related to algebra and polynomials. I would be very grateful if any of you could give a hand to solve it. Here is the problem: Consider the function $f_0(x) =x(1-x)$ and for ...
4
votes
0answers
185 views

Asymptotic behaviour of a two-dimensional recurrence relation

This problem comes out of a research in models of firm growth. The model is simple: A firm has two parameters which are its size (number of employees) and job vacancies. A firm of size $n$ will ...
4
votes
0answers
194 views

Is this a recurrence for the Mertens function plus 2?

If we define a symmetric array: $$T(1,1)=3,\; T(1,2)=2,\; T(2,1)=2$$ $$T(1,k)=\frac{-T(n,k-1)-\sum\limits_{i=2}^{k-1}T(i,k)}{k+1}+T(n,k-1)$$ $$ T(n,1)=\frac{-T(n-1,k)-\sum\limits_{i=2}^{n-1}T(n,i)}{...
3
votes
0answers
69 views

Solving a functional equation $2 f(2x)=f(x)(1+\cos(x))+f(x+\pi)(1-\cos(x))$

I am trying to solve the following functional equation, which appears in some of my physics calculations : $f(x)=\frac{1}{2}\left(f(\frac{x}{2})(1+\cos(\frac{x}{2}))+f(\frac{x}{2}+\pi)(1-\cos(\frac{x}...
3
votes
0answers
63 views

Asymptotics of the solution of $G_n(t) = \text{const}$, where $G_n(t) = e^t (1 + r^{-1}(G_{n-1}(t) - 1))^{r}$.

Consider a sequence of functions $(G_n(t))$ on $\Bbb{R}$ that satisfies the recurrence relation $$ G_0(t) = e^t, \qquad G_n(t) = e^t \left( 1 + \frac{G_{s-1}(t) - 1}{r} \right)^{r}. $$ for some ...
3
votes
0answers
85 views

Permutation and Combinatorics Problem

A function $G$ is defined on a set $S$ with size $k$ : $G(a_1,a_2,a_3,\ldots,a_k)$. $G(a_1,a_2,a_3,\ldots,a_k) = 1$ if and only if a convex polygon can be created by taking these $k$ elements as the ...
3
votes
0answers
68 views

Solve the Recurrence relation : $a_n= (a_{n-1})^3a_{n-2}$ , $a_0=1, a_1=3$

$a_n= (a_{n-1})^3a_{n-2}$ , $a_0=1, a_1=3$ I'm ask to get an expression for $a_n$. So i tried to solve with induction: $a_n=(a_{n-1})^3a_{n-2}=(a_{n-1})^3(a_{n-3})^3a_{n-4}=(a_{n-1})^3(a_{n-3})^3(...
3
votes
0answers
111 views

Asymptotic solutions of a sparsely perturbed recurrence relation

Recurrence relation I am trying to find approximate solutions $T(n)$ of the recurrence relation $$ p\ T(n-1) - \left[p+q+\overline{S} + \varepsilon \tilde{S}(n)\right]T(n) + q\ T(n+1) = 0,\\ \text{...
3
votes
0answers
46 views

Is this recurrence relation solvable?

Consider the following recurrence relation: \begin{equation} \gamma C_{m,n}+n\alpha C_{n,m}+ \beta \{C_{n+1,m}+ n C_{n-1,m}\}=EC_{n,m} \end{equation} where $\gamma, \alpha$ and $\beta$ are ...
3
votes
0answers
55 views

Solve recurrence relation merge sort

I'd like to know how I can solve a recurrence relation like the one from merge sort. I know how to solve recurrence equations that start with $a(n)=a(n-1)+(n-1)$, but I don't know how to solve ...
3
votes
0answers
126 views

Simplification of recursive polynomials

Suppose I have known polynomials $p_i, i=0\ldots k-1$. I have the following horrific looking recursive equation: $$p_{k}(x)=-\prod_{i=1}^{k}{(x+i)}^{\left\lfloor\frac{k}{i}\right\rfloor-1}\left[p_o(x)...
3
votes
0answers
50 views

Formula for numbers whose iterated distance from next square has fixed point $2$

Consider a function $R: \mathbb N \to \mathbb N,$ $R(n)$ is the distance to the next square greater or equal to $n$. For example, $R(5)=4$ and $R(16)=0.$ Function $R$ has two fixed points, $0$ and $...
3
votes
0answers
38 views

How to work with a recursive function with 2 recursive instances?

In class, we figured out how to find the closed form of a recursive definition through the "basic 5 steps method". Example function T(n): If n = 1, T(1) = 1 If n > 1, T(n) = T(n-1)+1 Step 1: ...
3
votes
0answers
118 views

How to solve this finite-difference equation?

How to solve the following finite-differences equation: $$f(x) = f(x-1) + f(x-\sqrt{2}), \quad x\in [\sqrt{2}, +\infty) \,?$$ Let's say $f(x) = f_0(x)$ for $x \in [0, \sqrt{2})$ is a given function. ...
3
votes
0answers
64 views

Showing that a number is part of sequence A000275 in OEIS

Consider the sequence of integers defined recursively by $c_0 = 1$ and $$ c_p = \sum_{l = 0}^{p-1} (-1)^{p+l+1} \binom{p}{l}^2 c_l $$ for $p \geq 1$. This is sequence A000275 in the online ...
3
votes
0answers
90 views

About linear recurrence sequences

Let $\{a_n\}_{n=0}^\infty$,$\{b_n\}_{n=0}^\infty$,$\{c_n\}_{n=0}^\infty$ be three complex sequences and satisfy \begin{eqnarray*} &&\sum_{k=0}^2\alpha_ka_{n+k}=0,\\ &&\sum_{k=0}^4\...
3
votes
0answers
174 views

Recursive Sequence from Finite Sequences

I'm searching for the name of these kind of sequences: Suppose you start off with a finite sequence containing one term: S0 = {3} To get the next sequence you ...
3
votes
0answers
108 views

How to resolve this equation for $f(n)$ without using $f(n-1)$

I have an equation related to some work I'm doing on Poisson distribution where I'm calculating a sequence of 100 values between a minimum and maximum value which is set by another formula. ...
3
votes
0answers
280 views

Two variable recurrence relations

I'm interested in solving the following type of problem... Starting with a recurrence relation in multiple variables, for example: $$ v_{i-1,j} + v_{i,j+1} + v_{i+1,j} + v_{i,j-1} = 4v_{i,j}$$ with ...
3
votes
0answers
731 views

recurrence relation with non constant coefficients

I'm trying to solve a second order differential equation and I got a recurrence. Can someone help to solve $$n(n-1+q)a_{n}-a_{n-3}+e\cdot a_{n-2}=0$$ where $q$, $e$, and $a_{0}$ are some real numbers ...