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

learn more… | top users | synonyms (2)

8
votes
0answers
187 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 ...
8
votes
0answers
118 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 ...
7
votes
0answers
113 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 ...
7
votes
0answers
98 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
100 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 ...
6
votes
0answers
109 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) = ...
6
votes
0answers
169 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 ...
6
votes
0answers
193 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 ...
5
votes
0answers
63 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 ...
5
votes
0answers
171 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 ...
5
votes
0answers
44 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 ...
5
votes
0answers
75 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
169 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 ...
4
votes
0answers
177 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
278 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
71 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
41 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
126 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
59 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
63 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
96 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
104 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
173 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
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
180 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
184 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
33 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
40 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
117 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
45 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
36 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
85 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
50 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
86 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
106 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
119 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 ...
3
votes
0answers
270 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
611 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 ...
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
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
0answers
17 views

Setting up a recurrence for Odd-Even Mergesort

Given the below algorithm How would one go about setting up a recurrence for both that merging algorithm AND using this "new" merging algorithm in a traditional merge sort? What I've tried For ...
2
votes
0answers
26 views

asymptotics of Involutions recurrence relation

Consider the following recurrence relation where $t(n)$ is the number of involutions on $\{1,...,n\}$ \begin{equation} (n+1)t(n)+t(n+1)-t(n+2)=0 \end{equation} When $n \rightarrow \infty$, Wimp and ...
2
votes
0answers
94 views

Number of unordered factorizations into $k$ distinct parts

Let $H_d(n)$ denote the number of distinct ordered factorizations of $n$ and $H_d(n,k)$ the number of ordered factorizations of $n$ into $k$ distinct parts. We have the following recurrence: ...
2
votes
0answers
38 views

Solving this recurrence relation representing constant-power loads on a resistive cable

Given the following: $$\begin{align} v_n&=v_{n-1}-r\sum_{i=n}^m \frac p{v_i}\\ v_0&=V \end{align}$$ where: $$\begin{align} m\ge n\ge 0\;&:\;m,\,n\in\mathbb {N_0}\\ ...
2
votes
0answers
40 views

How many entries in the sequence $x_n$ given by recursion $x_1=1\ ,\ x_{n+1}=p_{x_n}$ are known?

The sequence $x_n$ with the recursion $x_1=1\ ,\ x_{n+1}=p_{x_n}$ , where $p_k$ denotes the $k-th$ prime, has the following values : ...
2
votes
0answers
22 views

Determining asymptotics of a function given a series of difference-like inequalities

I have a function $f: \mathbb{R}_{\geq 0} \rightarrow \mathbb{R}_{\geq 0}$ and I know it satisfies the following properties. $f(x) \leq \frac{\log{\sqrt{2}}}{2x}$ and for all $A \geq 1$ and $B \geq ...
2
votes
0answers
20 views

Determining the sequence that yields a balanced search tree in the form of a recurrence / sequence

Let's say I have a sequence of (distinct) monotonically increasing numbers S. I'll want to add them sequentially to a Binary Search Tree (BST) but as the numbers ...
2
votes
0answers
42 views

Generating function for recurrence in two variables

Given characteristic polynomial for the recurrence in two variables (say $F(x,y)$) $$ (y^2-1)^x $$ and initial values can generating function for $F(x,y)$ be derived? I know how to do it for a ...
2
votes
0answers
38 views

Multivariable generating functions

Let's consider a 2-variable generating function for the Dyck triangle numbers. Reccurence, satisfying to the triangle conditions is $d_{n, k}=d_{n-1, k-1}+d_{n-1, k}+d_{n-1, k-1}$, $d_{0, 0}=1$, ...
2
votes
0answers
67 views

Derive a Recurrence

Could really use some help with this. For an integer $m \geq 1$ and $n \geq 1$, consider $m$ horizontal lines and $n$ non-horizontal lines, such that no two of the non-horizontal lines are parallel ...