Questions regarding functions defined recursively, such as the Fibonacci sequence.
27
votes
2answers
396 views
Very curious properties of ordered partitions relating to Fibonacci numbers
I came across some interesting propositions in some calculations I did and I was wondering if someone would be so kind as to provide some explanations of these phenomenon.
We call an ordered ...
22
votes
4answers
448 views
Evaluating $\sqrt{1 + \sqrt{2 + \sqrt{4 + \sqrt{8 + \ldots}}}}$
Inspired by Ramanujan's problem and solution of $\sqrt{1 + 2\sqrt{1 + 3\sqrt{1 + \ldots}}}$, I decided to attempt evaluating the infinite radical
$$
\sqrt{1 + \sqrt{2 + \sqrt{4 + \sqrt{8 + \ldots}}}}
...
21
votes
1answer
420 views
Is $\sin\left(\frac{\pi}{2}\sin\left(\frac{\pi}{2}\cdots\sin x\cdots\right)\right)=\frac4{\pi}\sum\limits_{k=0}^\infty\frac{\sin(2k+1)x}{2k+1}$?
We can see intuitively that
$$
f(x)=\sin\left(\frac{\pi}{2}\sin\left(\frac{\pi}{2}\sin\left(\frac{\pi}{2}\cdots\sin{x}\cdots\right)\right)\right)
$$
is the square wave with period $2\pi$ and has the ...
19
votes
4answers
398 views
recurrence relation arising from Magic the Gathering scenario [duplicate]
Possible Duplicate:
Probability of a random binary string containing a long run of 1s?
EDIT: Cocopuffs below has partially answered the question, but the critical base case $L=2$ to his ...
17
votes
5answers
2k views
Number of ways to partition a rectangle into n sub-rectangles
How many ways can a rectangle be partitioned by either vertical or horizontal lines into n sub-rectangles? At first I thought it would be:
...
17
votes
3answers
814 views
Self-avoiding walk on $\mathbb{Z}$
How many sequences $a_1,a_2,a_3,\dotsc$, satisfy:
i) $a_1=0$
ii) ($a_{n+1}=a_n-n$ or $a_{n+1}=a_n+n$)
iii) $a_i\neq a_j$ for $i\neq j$
iiii) $\mathbb{Z}=\{a_i\}_{i>0}$
Are the two alternating ...
16
votes
5answers
371 views
limit of : $a_{n+2} =\frac{1}{a_n} + \frac{1}{a_{n+1}}$
$a_n$ is a real sequence, $a_1,a_2$ are positive and for all $n>2$ : $$ a_{n+2} =\frac{1}{a_{n+1}} + \frac{1}{a_{n}}.$$
Prove that: $\displaystyle \lim_{n\to \infty} a_n$ exists, then find it.
...
16
votes
3answers
284 views
Counting binary sequences with no more than $2$ equal consecutive numbers
I invented the following problem, but I can't solve it.
There are $n$ $1$'s and $n$ $0$'s and my question is what is the number of ways to arrange them avoiding $3$ equal consecutive numbers.
So for ...
15
votes
5answers
769 views
Find a closed form for this sequence: $a_{n+1} = a_n + a_n^{-1}$
Today, we had a math class, where we had to show, that $a_{100} > 14$ for
$$a_0 = 1;\qquad a_{n+1} = a_n + a_n^{-1}$$
Apart from this task, I asked my self: Is there a closed form for this ...
15
votes
2answers
472 views
Probability of a random binary string containing a long run of 1s?
For some fixed $n$, let $p_n$ be the probability that a random infinite binary string contains a run of consecutive $1$s, containing $n$ more $1$s than the total number appearing before the run.
For ...
14
votes
4answers
254 views
Solve recursion $a_{n}=ba_{n-1}+cd^{n-1}$
Let $b,c,d\in\mathbb{R}$ be constants with $b\neq d$. Let
$$\begin{eqnarray}
a_{n} &=& ba_{n-1}+cd^{n-1}
\end{eqnarray}$$
be a sequence for $n \geq 1$ with $a_{0}=0$. I want to find a closed ...
14
votes
2answers
309 views
Solving the recurrence relation $a_n=\frac{a_{n-1}^2+a_{n-2}^2}{a_{n-1}+a_{n-2}}$
I would like to know if there is a way to get the recurrence relation
$$a_n=\frac{a_{n-1}^2+a_{n-2}^2}{a_{n-1}+a_{n-2}},\qquad (a_1=1,a_2=2)$$
in closed form, or if there is no such way, how one could ...
13
votes
3answers
454 views
Finding an Explicit Formula from the Recurrence: $na_{n}= 2 ( a_{n-1}+a_{n-2})$
Here is the recurrence:
$$na_{n}=2(a_{n-1}+a_{n-2}) \qquad\text{ where } a_{0}=1\text{ and }a_{1}=2$$
At first I thought that this could be easily solved by simply multiplying the Fibonacci ...
13
votes
3answers
396 views
Solving a difficult recursion via generating functions
I have been trying to solve the recurrence:
\begin{align*}
a_{n+1}=\frac{2(n+1)a_n+5((n+1)!)}{3},
\end{align*}
where $a_0=5$, via generating functions with little success. My progress until now is ...
13
votes
3answers
241 views
A recurrence relation for the Harmonic numbers of the form $H_n = \sum\limits_{k=1}^{n-1}f(k,n)H_k$
Working on Harmonic numbers, I found this very interesting recurrence relation :
$$
H_n = \frac{n+1}{n-1} \sum_{k=1}^{n-1}\left(\frac{2}{k+1}-\frac{1}{1+n-k}\right)H_k
,\quad \forall\ ...
12
votes
6answers
601 views
How to solve this recurrence relation? $f_n = 3f_{n-1} + 12(-1)^n$
How to solve this particular recurrence relation ?
$$f_n = 3f_{n-1} + 12(-1)^n,\quad f_1 = 0$$
such that $f_2 = 12, f_3 = 24$ and so on.
I tried out a lot but due to $(-1)^n$ I am not able to ...
12
votes
5answers
301 views
Alternate proof that for every natural number $n,\ \left\lfloor\left(\frac{7+\sqrt{37}}{2}\right)^n\right\rfloor$ is divisible by $3$
Original Problem:
Prove that for every natural number $n$,$$\left\lfloor\left(\frac{7+\sqrt{37}}{2}\right)^n\right\rfloor$$ is divisible by $3$.
I found the problem in the book Winning ...
12
votes
5answers
277 views
Solve the sequence : $u_n = 1-(\frac{u_1}{n} + \frac{u_2}{n-1} + \ldots + \frac{u_{n-1}}{2})$
For a physical model I am trying to solve this sequence:
$$\begin{align*}
u_1 &= 1 \\
u_2 &= 1-\left(\frac{u_1}{2}\right) \\
u_3 &= 1-\left(\frac{u_1}{3} + \frac{u_2}{2}\right) \\
u_4 ...
12
votes
2answers
441 views
Zeroes of the third derivative of an iterated sine.
I've been playing with the functions $$f_n:[0,\pi/2]\to[0,1]\\\begin{cases} f_1&=&\sin\\f_{n+1}&=&\sin\circ f_n\end{cases}.$$ A simple argument proves that $f_n(x)\to 0$ for $x\in ...
11
votes
2answers
245 views
Generalized Fibonacci Sequence Question
The Fibonacci Sequence is defined as the recurrence
$a(n)=a_{n-1}+a_{n-2}$ where $a(0)=0$ and $a(1)=1$. Today, I was bored so I considered the sequence $a(n)=\sqrt{a_{n-1}}+\sqrt{a_{n-2}}$. Ten ...
11
votes
1answer
141 views
Integer Sequence “sums of digits of squares”.
For all $n \in \mathbb{N}$ we define the function $\delta(n)=p$, where $p$ is sums of digits of $n^2$. For example if $n=17, \ n^2=289$, then $\delta(17)=2+8+9=19$.
Let $a_k$ is a monotonically ...
11
votes
2answers
206 views
How to find a “better description” (e.g. recurrence relation) for this sequence?
My solution to a problem in Project Euler required to solve this subproblem: find values of $k\in\mathrm{N}$ such that $3k^2+4$ is a perfect square.
As I was writting a computer program, I just tried ...
10
votes
3answers
372 views
prove $\sqrt{a_n b_n}$ and $\frac{1}{2}(a_n+b_n)$ have same limit
i am given this problem:
let $a\ge0$,$b\ge0$, and the sequences $a_n$ and $b_n$ are defined in this way: $a_0:=a$, $b_0:=b$ and $a_{n+1}:= \sqrt{a_nb_n}$ and $b_{n+1}:=\frac{1}{2}(a_n+b_n)$ for all ...
10
votes
3answers
766 views
Stirling number of the first kind: Proof of Recursion formula
I want to prove this recursion formula for Stirling numbers of the first kind:
$$s_{n+1,k+1} = \sum_{i=k}^{n} \binom{i}{k} s_{n,i}$$
But I lack a useful idea. Perhaps someone could inspire me?
...
10
votes
1answer
242 views
Why do the Fibonacci numbers recycle these formulas?
The Fibonacci numbers $F_n = 0, 1, 1, 2, 3, 5, 8, 13, \dots$
obey the following recurrence relations,
$ \begin{aligned}
&F_{n}-\;F_{n-1}-F_{n-2} = 0\\[1.5mm]
&F_{n-1}^3-F_{n}^3-F_{n+1}^3 = ...
10
votes
1answer
2k views
Odd and even numbers in Pascal's triangle-Sierpinski's triangle
Moderator Note: At the time that this question was posted, it was from an ongoing contest. The relevant deadline has now passed.
I recently learned that when the Pascal's triangle is reduced ...
10
votes
1answer
287 views
Solving a Nonlinear Recursion
In the course of some research computations I have been doing, I run up against a recursion
$$ a_{n+3} = a_{n+2}a_{n+1} - a_n $$
I've tried to find out if it's possible to solve recursions of this ...
10
votes
1answer
238 views
Using Dyson's conjecture to give another proof of Dixon's identity.
For natural numbers $a_1,\dots,a_n$, Freeman Dyson conjectured (and it was eventually proven) that the Laurent polynomial
$$
\prod_{i,j=1\atop i\neq j}^n\left(1-\frac{x_i}{x_j}\right)^{a_i}
$$
has ...
10
votes
1answer
149 views
Solve $A_n=A_{n-1}+\lfloor \sqrt{A_{n-1}}\rfloor$
I am trying to solve the recurrence:
$A_0=1$
$A_n=A_{n-1}+\lfloor \sqrt{A_{n-1}}\rfloor,\text{ for } n > 0$
Its obvious that
$A_n=m^2 \implies A_{n+1}=m^2+m$
however my book's solution states ...
9
votes
3answers
296 views
Solving the recurrence relation $A_n=n!+\sum_{i=1}^n{n\choose i}A_{n-i}$
I am attempting to solve the recurrence relation $A_n=n!+\sum_{i=1}^n{n\choose i}A_{n-i}$ with the initial condition $A_0=1$. By "solving" I mean finding an efficient way of computing $A_n$ for ...
9
votes
1answer
262 views
Recurrence for the partition numbers
I'm reading Analytic Combinatorics [PDF] book by Flajolet and Sedgewick, and I can't figure out one of the steps in the derivation of the $P_n$ — number of partitions of size $n$ (or coefficients in ...
9
votes
2answers
85 views
Proving that $a_n$ is an integer for every $n$
For every $k\ge1$ integer number if we define the sequence : $a_1,a_2,a_3,...,$ in the form of :$$a_1=2$$
$$a_{n+1}=ka_n+\sqrt{(k^2-1)(a^2_n-4)}$$
For every $n=1,2,3,....$ how to prove that $a_n$ is ...
9
votes
3answers
368 views
Solving randomized recurrence relation
I'm looking at the random sequence $x_n$ with $x_0=x_1=1$ and
\begin{equation}
x_{n+1}=2x_n\pm x_{n-1}
\end{equation}
where we choose the $\pm$ sign independently with equal probability. Now ...
8
votes
2answers
525 views
Solving recurrence relations that involve all previous terms
I'm not sure if this a proper recurance relation per se but I'd be interested in the methodology in solving a recurrence relation of the following form:
$Z_0 = 1$
$Z_1 = x_1$
$Z_2 = x_1Z_1 + x_2 = ...
8
votes
4answers
348 views
Closed form for a non-linear recurrence
Does equation $a_n=\sqrt{a_{n-1}+6}$ with $a_1=6$ have a closed form? I've found no linearization method. Any suggestion or hint will be highly appreciated.
8
votes
1answer
98 views
Möbius function from random number sequence
Consider some arbitrary number sequence like the decimal expansion of $\pi$ = {3, 1, 4, 1, 5, 9, 2}. Prepend the sequence with the number $1$ so that you get {1, 3, 1, 4, 1, 5, 9, 2}.
Then plug it ...
8
votes
1answer
119 views
Prove that a holonomic (p-recursive) difference equation returns only integral values
Consider the recurrence given by
$(n+1)^2 a_{n+1} = (9n^2+9n+3)a_n-27n^2 a_{n-1}$
$a_0 = 1, a_1 = 3$.
Clearly, $a_n$ is rational, but unexpectedly, the recurrence seems to output only integral ...
8
votes
1answer
389 views
How to solve this recurrence
Solve the recurrence
\[
f_{j,k}^{(l)} =
\begin{cases}
\left[j>k\right] j^{k-1}(j-k), &\qquad j=l \\
\\
\left[j>k+1\right] \sum_t \binom k t f_{j-1,k-t}^{(l)}, &\qquad j>l
\end{cases}
...
8
votes
0answers
121 views
A series: $1-\frac{1}{2}-\frac{1}{3}-\frac{1}{4}+\frac{1}{5}-\frac{1}{6}+\frac{1}{7}+\cdots$
Denote $$b_1=1,b_{n}=b_{n-1}-\dfrac{S(b_{n-1})}{n},(n>1 )\tag1$$
where $S(x)=1$ if $x>0,S(x)=-1$ if $x<0$, and $S(0)=0.$
So ...
7
votes
8answers
593 views
Need help deriving recurrence relation for even-valued Fibonacci numbers.
That would be every third Fibonacci number, e.g. $0, 2, 8, 34, 144, 610, 2584, 10946,...$
Empirically one can check that:
$a(n) = 4a(n-1) + a(n-2)$ where $a(-1) = 2, a(0) = 0$.
If $f(n)$ is ...
7
votes
4answers
868 views
How to find the closed form formula for this recurrence relation
$ x_{0} = 5 $
$ x_{n} = 2x_{n-1} + 9(5^{n-1})$
I have computed: $x_{0} = 5, x_{1} = 19, x_{2} = 83, x_{3} = 391, x_{4} = 1907$, but cannot see any pattern for the general $n^{th}$ term.
7
votes
6answers
303 views
Finding the $n$-th deriviative of $f(x) =e^x \sin x$, solving the recurrence relation
I was given a homework assignment to find a closed solution for the nth deriviative of the function:
$f(x) = e^x \sin x$
So far I have been able to obtain the derivative as:
$f^{(n)}(x) = e^x S_n ...
7
votes
2answers
415 views
Reduction formula for $I_{n}=\int {\cos{nx} \over \cos{x}}\rm{d}x$
What would be a simple method to compute a reduction formula for the following?
$\displaystyle I_{n}=\int {\cos{nx} \over \cos{x}} \rm{d}x~$ where $n$ is a positive integer
I understand that it ...
7
votes
1answer
179 views
Finding $a_n$ for very large $n$ where $a_n = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3} $
I have a recurrence relation,
$$ a_n = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3} $$
for $n>3$ and $a_1 = 0, a_2 = 0, a_3 = 1$
I have to find the value of $a_n$ for very large values of n. I tried ...
7
votes
1answer
124 views
Put a mouse to the last cell
We have (n=12) cells $C_1, C_2 ,\dots, C_{12}$ which are initially empty.
At each step, we can do one of two operations:
$\mathbf{P}$: Put only in the first cell $C_1$ 2 mice.
$\mathbf{M}$: Move ...
7
votes
2answers
217 views
q-Analogue of the formula $x^n=\sum_k\left\{n\atop k\right\}(x)_k$.
The stirling numbers of the second kind satisfy the formula $x^n=\sum_k\left\{n\atop k\right\}(x)_k$, where $(x)_k$ is the falling factorial.
Consider the $q$-analog recursive definition of the ...
7
votes
1answer
163 views
Diagonal of the double sequence $(n+1)v_{h,n+1}-(2h+1)v_{h,n}-nv_{h,n-1}=0$
Update: it is not possible to reply to this question without additional information.
My comment below: "I have to agree with you that one "cannot derive (2) from (1) alone". Now it seems to me that ...
6
votes
5answers
181 views
How can I find the value of $a^n+b^n$, given the value of $a+b$, $ab$, and $n$?
I have been given the value of $a+b$ , $ab$ and $n$. I've to calculate the value of $a^n+b^n$. How can I do it?
I would like to find out a general solution. Because the value of $n$ , $a+b$ and $ab$ ...
6
votes
5answers
366 views
How does one find a formula for the recurrence relation $a_{1}=1,a_{2}=3, a_{n+2}=a_{n+1}+a_{n}?$
I am self-studying Discrete Mathematics, and I have two exercises to solve.
Find a formula for the following recurrence relation: (translated from Portuguese)
a) $a_{1}=3,a_{2}=5, ...
6
votes
4answers
123 views
closed form for $d(4)=2$, $d(n+1)=d(n)+n-1$?
I am helping a friend in his last year of high school with his math class. They are studying recurrences and proof by inference. One of the exercises was simply "How many diagonals does a regular ...
