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

learn more… | top users | synonyms

9
votes
0answers
248 views

Generating function solution to previous question $a_{n}=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3 \rfloor}+a_{\lfloor n/6\rfloor}$

In attempting to answer this question, I reduced it to a seemingly simple generating functions question, but after days of work was unable to construct a proof. Since I do not have experience trying ...
7
votes
0answers
78 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 ...
7
votes
0answers
218 views

How does one prove that $\zeta(3)$ is irrational?

How does one prove that $\zeta(3)$ is irrational ? I would like to know how Apery did it. In particular how a recursion gives rise to irrationality !?
6
votes
0answers
39 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 ...
6
votes
0answers
155 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
34 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
53 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
73 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 ...
5
votes
0answers
118 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
506 views

The Average Running Time Of Euclid Algorithm?

What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$? It seems very hard to deduce from the recurrence $T(m,n) = T(n, m ...
4
votes
0answers
29 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
65 views

Nonlinear inhomogeneous recurrence $f(x)^2=f(x+1)+S(x)$

I want to solve the recurrence relation $$f(x)^2=f(x+1)+S(x)$$ where $S(x)$ is a given polynomial. I am especially interested in the case $$S(x)=\tfrac{1}{2}x^2+\tfrac{1}{2}x.$$ I have no ...
4
votes
0answers
50 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
89 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
156 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 ...
4
votes
0answers
176 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
165 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
174 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
44 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
32 views

Finding a Solution for a Chebyshev-like Recurrence

It is while studying the Hückel Method of Physical Chemistry that I came across the following recurrence relation: \begin{align*} U_n(x)=xU_{n-1}(x)-U_{n-2}(x)+(-1)^{n-1}(4+2x) \end{align*} Where ...
3
votes
0answers
100 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
99 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
237 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
57 views

An interesting partial recurrence equation

What is the closed form solution to the following partial recurrence relation? $$f(k,n) = \sum\limits_{t=0}^{m}f(k-t, n-1),$$ where $ m \geq 0$ is some fixed parameter. The boundary values are ...
3
votes
0answers
386 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
426 views

Solving recurrences of the form $T(n)=aT(n/a)+Θ(nlgn)$

On pages 95 and 96 of the third edition of the CLRS book, we find the following, which applies here since $a=b$ is all it takes to block the application of the Master Theorem: "Although $n\lg n$ is ...
3
votes
0answers
57 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
26 views

Verify that this recurrence relation is in O(log n)

For the recurrence $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ is in $\Theta(lg n)$ My attempt at a solution (mostly just wanting to verify its correct). Lower Bound: $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ ...
2
votes
0answers
92 views

How to solve a ceiling expression or recurrence equation?

I am trying to express the following in term of n, $$\underbrace{\hbox{$ \left \lceil \frac{3}{2}.\left \lceil { \frac{3}{2}.\left \lceil { \ldots \left \lceil \frac{3}{2}.\left \lceil { ...
2
votes
0answers
134 views

Special map $f(x_n)=x_{{n+1} [\mod 4]}$

As mentioned in the headline I am considering the map $f(x_n)=x_{{n+1} [\mod 4]}$. It looks a little bit similar to the dyadic (bernoulli) map but instead of $\mod 1$ we have $\mod 4$ which means that ...
2
votes
0answers
44 views

(limit of) a linear second order recurrence relation with variable coefficients

I have the following recurrence relation: $(n + 1) a_{n + 2} = (w (n + 1) - c) a_{n + 1} - z (n + 1)*a_{n}$ that I would like to either solve, or to get the $n$ goes to Infinity limit of the ratio ...
2
votes
0answers
163 views

Induction proof of a recurrence relation

I have some trouble with an induction proof for the following problem. There is a vending machine that only takes coins of value 1 and 5 respectively. Let $S_n$ be the number of different ...
2
votes
0answers
29 views

Determinant of Stirling submatrix

Consider the table containing the Stirling numbers of the second kind $S\left( n,k\right) $. From this table construct a square matrix $M$ containing $N$ differents rows from the table ...
2
votes
0answers
83 views

How to solve this recurrence relation (related to discrete Fourier transform)?

I am having trouble with the following recurrence relation: $$c_{n+1} - c_{n-1} = 2\alpha \sin \frac{(2n-1)\pi}{N} c_n, \quad\forall n \in \mathbb{Z},$$ where $N$ is odd and the initial condition is ...
2
votes
0answers
52 views

Recurrence relation for polygamma reflection polynomials

In the reflection formula for the polygamma function $$ \psi^{(n)}(1-z) + (-1)^{n+1}\psi^{(n)}(z) % = (-1)^{n} \pi \frac{d^{n}}{d z^{n}} \cot (\pi z) $$ the right hand side is a polynomial ...
2
votes
0answers
90 views

Showing the relationship between Lucas and Fibonacci numbers with a recursive relationship

Given the equation $$L_{n+k}-(-1)^kL_{n-k}=5F_kF_n$$ Where $\{L\}$ is the set of Lucas numbers and $\{F\}$ is a Fibonacci sequence, $n$ and $k$ are both $>0$ and integers, how would one develop ...
2
votes
0answers
69 views

How prove this sequences have limts and find this value?

let $f:R\longrightarrow R$,and $f(x)=x-\dfrac{x^2}{2}$,and $$L_{1}(x)=f(x),L_{2}(x)=f(f(x)),L_{3}(x)=f(L_{2}(x)),\cdots,L_{n}(x)=f(L_{n-1}(x))$$ and let $$a_{n}=L_{n}\left(\dfrac{17}{n}\right)$$ ...
2
votes
0answers
51 views

Finding the best real value for $C$.

Consider the recurrence $f_{n+1}=f_n + \ln(f_n)$ with $f_0=2$. Also consider differential equations of type $g(0)=2$ and $\dfrac{d g}{d x}=\ln(g(x)- C \cdot \ln(g(x)))$. Lets call the solution ...
2
votes
0answers
63 views

Solving recurrence relation of algorithm complexity?

Supposing I write an algorithm that results into this kind of recurrence relation $$\left\{ \begin{array}{ll} T(0)=T(1)=1 \\ T(n)=T\left(\lfloor n/2 \rfloor \right)+T\left(\lceil n/2 ...
2
votes
0answers
113 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 ...
2
votes
0answers
96 views

Is there a closed form for this recurrence?

Given $$ E_{n,k} = \begin{cases} 0 & \text{ if } n \leq k \\ n & \text{ if } k = 0 \\ \sum_{i=0}^{n-1} \dfrac{1}{n} \cdot E_{i,k-1} & \text{ otherwise } \end{cases} $$ I wonder is there ...
2
votes
0answers
65 views

How much information do I gain from each modular inequality?

Problem details: Let $p = 2^{48}$, $s\leftarrow\{0,1\}^{48}$, and $a,b$ known constants. Furthermore let $f(x) = a x + b \pmod{p}$ and let the value $r_k$ be defined by the first-order recurrence ...
2
votes
0answers
53 views

how to compute $\lim_{n\to\infty}\ln(f(n))/\ln(n)$ for this given $f(n)$?

Let $c=f(0)$ be a real number and $n,m$ positive integers. Let $P_k(n)$ be integer polynomials of $n$. Let $f(n)$ be defined by the recursion $\left[\sum_{k=0}^{m} P_k(n)f(n+k)\right]+P_{-1}(n)=0$. ...
2
votes
0answers
525 views

Probability of tossing a biased coin without having k heads consecutively in a row

I got asked by a friend this question; I have a coin, the probability of receiving a head by tossing is $p$ and tail $1-p$. I have to toss it $n$ times without getting $k$ heads in a row. What is the ...
2
votes
0answers
408 views

How to solve non-linear recurrence relation in general?

For linear recurrence, we can use generating function. So is there a general technique to solve non-linear recurrence or it depends on a specific sequence? For example, $$a_{n+1} = \dfrac{a_n(a_n - ...
2
votes
0answers
239 views

Linear multivariate recurrences with constant coefficients

In the theory of univariate linear recurrences with constant coefficients, there is a general method of solving initial value problems based on characteristic polynomials. I would like to ask, if any ...
2
votes
0answers
92 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(\frac{-n}{3}, \frac{1-n}{3}, \frac{2-n}{3};\; \frac{1-n}{2}, \frac{2-n}{2};\; -\frac{3^3}{2^2}) = 1, 1, ...
2
votes
0answers
217 views

Solving two-parameter linear recurrence with different initial values

I'm looking for a method to solve the well-known recurrence ralation with different initial values. The one-parameter linear recurrence is easier. Let's take a peek: $a_0 = \alpha$; $a_1 = \beta$; ...
2
votes
0answers
169 views

How to solve the recursive relation in Kalman filter?

I was wondering how to solve the Kalman filter's recursive equation (also see the appendix at the end of this post) for the estimated state $\hat{\textbf{x}}_{n|n}$ at time $n$, over discrete times ...
2
votes
0answers
70 views

Construction of polynomials with non-commutative elements.

I have a simple set of polynomials which I know how to construct for each integer $n$, but I havn't been able to write them down in terms of concrete sums and products. For $n\in\mathbb N_+$, we have ...