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

learn more… | top users | synonyms (2)

35
votes
0answers
572 views

Mirror algorithm for computing $\pi$ and $e$ - does it hint on some connection between them?

Benoit Cloitre offered two 'mirror sequences', which allow to compute $\pi$ and $e$ in similar ways: $$u_{n+2}=u_{n+1}+\frac{u_n}{n}$$ $$v_{n+2}=\frac{v_{n+1}}{n}+v_{n}$$ $$u_1=v_1=0$$ ...
10
votes
0answers
239 views

Mathematics of the Ice Bucket Challenge

I've been considering the mathematics of the now global ice bucket challenge. Simple model In the simplest incarnation, there is one original seed, who then nominates 3 others, each of which take ...
10
votes
0answers
178 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 ...
9
votes
0answers
263 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
128 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
75 views

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 not ...
7
votes
0answers
40 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
61 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
125 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
118 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
178 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
107 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
264 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
54 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 ...
6
votes
0answers
79 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. ...
5
votes
0answers
218 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
202 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), ...
5
votes
0answers
729 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 ...
4
votes
0answers
58 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 ...
4
votes
0answers
186 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} ...
4
votes
0answers
99 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
51 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
170 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
99 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
116 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
132 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
191 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)$$ $$ ...
3
votes
0answers
165 views
+100

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 ...
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
79 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
65 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: ...
3
votes
0answers
110 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,\\ ...
3
votes
0answers
44 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
50 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: ...
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
110 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
63 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
89 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,\\ ...
3
votes
0answers
170 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
279 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
63 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 ...