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

learn more… | top users | synonyms (2)

62
votes
3answers
1k views

How prove this nice limit $\lim_{n\to\infty}\frac{a_{n}}{n}=\frac{12}{\log{432}}$

Nice problem: Let $a_{0}=1$ and $$a_{n}=a_{\left\lfloor n/2\right\rfloor}+a_{\left\lfloor n/3 \right\rfloor}+a_{\left\lfloor n/6\right\rfloor}.$$ Show that ...
39
votes
5answers
2k views

How much weight is on each person in a human pyramid?

After participating in a human pyramid and learning that it's very uncomfortable to have a lot of weight on your back, I figured I'd try to write out a recurrence relation for the total amount of ...
33
votes
6answers
5k views

Proof the Fibonacci numbers are not a polynomial.

I was asked a while ago to prove there is no polynomial $P$ in $\mathbb R$ such that $P(i)=f_i$ for all $i\geq0$. I tried to get a proof as slick as possible and here's what I got. Let ...
33
votes
1answer
825 views

Finding the sum- $x+x^{2}+x^{4}+x^{8}+x^{16}\cdots$

If $S = x+x^{2}+x^{4}+x^{8}+x^{16}\cdots$ Find S. Note:This is not a GP series.The powers are in GP. My Attempts so far: 1)If $S(x)=x+x^{2}+x^{4}+x^{8}+x^{16}\cdots$ Then ...
32
votes
4answers
2k views

A stronger version of discrete “Liouville's theorem”

If a function $f : \mathbb Z\times \mathbb Z \rightarrow \mathbb{R}^{+} $ satisfies the following condition $$\forall x, y \in \mathbb{Z}, f(x,y) = \dfrac{f(x + 1, y)+f(x, y + 1) + f(x - 1, y) +f(x, ...
32
votes
3answers
773 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 ...
31
votes
2answers
691 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 ...
28
votes
2answers
1k views

Limit of recursive sequence $a_{n+1} = \frac{a_n}{1- \{a_n\}}$

Consider the following sequence: let $a_0>0$ be rational. Define $$a_{n+1}= \frac{a_n}{1-\{a_n\}},$$ where $\{a_n\}$ is the fractional part of $a_n$ (i.e. $\{a_n\} = a_n - \lfloor a_n\rfloor$). ...
28
votes
1answer
961 views

This one weird thing that bugs me about summation and the like

Most of us know $$\sum_{n=a}^b c_n=c_a+c_{a+1}...+c_{b-1}+c_b$$ Some of us know $$\prod_{n=a}^b c_n=c_a \cdot c_{a+1}...c_{b-1} \cdot c_{b}$$ A few of us know ...
27
votes
2answers
562 views

How to calculate $\sum_{n=1}^\infty\frac{(-1)^n}n H_n^2$?

I need to calculate the sum $\displaystyle S=\sum_{n=1}^\infty\frac{(-1)^n}n H_n^2$, where $\displaystyle H_n=\sum\limits_{m=1}^n\frac1m$. Using a CAS I found that $S=\lim\limits_{k\to\infty}s_k$ ...
26
votes
3answers
570 views

Finding every $n$ such that $a_n$ is an integer

Let us define $\{a_n\}$ as $a_1=a_2=1$,$$a_{n+2}=a_{n+1}+\frac{a_n}{2}\ \ (n=1,2,\cdots).$$ Then, is the following conjecture true? A conjecture : If $a_n$ is an integer, then $n\le 8$. I ...
24
votes
2answers
570 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 ...
21
votes
4answers
594 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
3k views

Connection between the Laplace transform and generating functions

As I was sitting through a boring lecture rehashing basic techniques to solve ordinary differential equations, I began thinking about the Laplace transform and scribbled down a few ideas that I've ...
20
votes
5answers
1k views

Closed form for the sequence defined by $a_0=1$ and $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 myself: Is there a closed form for this ...
20
votes
6answers
734 views

Why does every “fibonacci like” series converge to $\phi$?

It's is well known that the ratio of side-by-side fibonacci numbers converge to $\phi$. But it seems by my calculations, that if one starts with any pair of numbers one will also get a ratio that ...
20
votes
2answers
1k 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 ...
20
votes
1answer
469 views

Infinite staircase to a circle

Suppose you start at $(0,0)$ on the unit disc and repeat the following procedure again and again: Face east and walk half-way to the circumference. Face north and walk half-way to the circumference. ...
20
votes
2answers
429 views

What is the integral of $e^{a \cdot x+b \cdot y}$ evaluated over the Koch Curve

What is $$\int_{K} e^{a \cdot x+ b \cdot y} \mu(x,y)$$ where $K$ is the Koch curve and $\mu(x,y)$ is a uniform measure look here. Attempt: I can evaluate the integral numerically and I have derived ...
19
votes
4answers
485 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 ...
19
votes
2answers
889 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 ...
18
votes
4answers
4k 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: ...
18
votes
3answers
602 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 ...
17
votes
3answers
928 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 ...
17
votes
1answer
286 views

Show that $\lim\limits_{n\to\infty}\frac{a_1+a_2+\dots+a_n}{n^2}$ exists and is independent of the choice of $a$

Suppose $f:\mathbb{R}\to\mathbb{R}$ has period 1, and for some $q\in(0,1)$: $$|f(x)-f(y)|\leq q|x-y|\quad \forall x,y$$ Let $g(x)=x+f(x)$, for any $a\in\mathbb{R}$,define the following sequence: ...
16
votes
3answers
883 views

Solving the recursion $3a_{n+1}=2(n+1)a_n+5(n+1)!$ 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 ...
16
votes
2answers
2k views

Explicit formula for Bernoulli numbers by using only the recurrence relation

It is not hard to show, by induction on $m\in\mathbb N$, that there exist a sequence $(B_n)_{n\geq0}$ of rational numbers such that ...
16
votes
4answers
1k views

Converting recursive equations into matrices

How do we convert recursive equations into matrix forms? For instance, consider this recursive equation(Fibonacci Series): $$F_n = F_{n-1} + F_{n-2}$$ And it comes out to be that the following that ...
16
votes
2answers
338 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 ...
15
votes
4answers
952 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 ...
15
votes
4answers
335 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 ...
15
votes
5answers
834 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. ...
15
votes
2answers
268 views

How to prove that $a_{n}$ must be of the form $a^2+b^2$?

let $a_{1}=1,a_{2}=2,a_{3}=5$,and $$a_{n}=3a_{n-1}a_{n-2}-a_{n-3}$$ show that $a_{n}=a^2+b^2,a,b\in N$ while $a_{1}=0^2+1^2,a_{2}=2=1^2+1^2,a_{3}=5=2^2+1^2,a_{4}=29=5^2+2^2,a_{5}=433=17^2+12^2$ and ...
15
votes
2answers
552 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 ...
14
votes
6answers
2k 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 ...
14
votes
5answers
464 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 ...
14
votes
3answers
5k views

Solving recurrence relation in 2 variables

We already know how to solve a homogeneous recurrence relation in one variable using characteristic equation. Does a similar technique exists for solving a homogeneous recurrence relation in 2 ...
14
votes
4answers
495 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\ ...
14
votes
1answer
2k 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 ...
13
votes
5answers
460 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 ...
13
votes
3answers
248 views

For $x_{n+1}=x_n^2-2$, show $\lim_{n\to\infty}\frac{x_n}{x_0x_1\cdots x_{n-1}}=2$

Suppose $x_0:=2\sqrt{2}$ and $x_{n+1}=x_n^2-2$ for $n\ge1$. We have to show $$\lim_{n\to\infty}\frac{x_n}{x_0x_1\cdots x_{n-1}}=2$$ Establishing convergence is pretty direct but I'm having trouble ...
13
votes
2answers
3k views

Evaluating the limit of a sequence given by recurrence relation $a_1=\sqrt2$, $a_{n+1}=\sqrt{2+a_n}$. Is my solution correct?

Problem The sequence $(a_n)_{n=1}^\infty$ is given by recurrence relation: $a_1=\sqrt2$, $a_{n+1}=\sqrt{2+a_n}$. Evaluate the limit $\lim_{n\to\infty} a_n$. Solution Show that the sequence ...
13
votes
1answer
6k 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 ...
13
votes
2answers
599 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 ...
13
votes
1answer
236 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 ...
13
votes
2answers
2k views

Exact probability of random graph being connected

The problem: I'm trying to find the probability of a random undirected graph being connected. I'm using the model $G(n,p)$, where there are at most $n(n-1) \over 2$ edges (no self-loops or duplicate ...
12
votes
2answers
438 views

Finding the limits

Suppose $a_1=1, a_{k+1}=\sqrt{a_1+a_2+\cdots +a_k}, k \in \mathbb{N}$. Find the limits $$i)\space \lim_{n\to\infty}\displaystyle \frac{\sum_{k=1}^{n} a_{k}}{n\sqrt{n}}$$ $$ii)\space ...
12
votes
3answers
924 views

Recursive Integration over Piecewise Polynomials: Closed form?

Is there a closed form to the following recursive integration? $$ f_0(x) = \begin{cases} 1/2 & |x|<1 \\ 0 & |x|\geq1 \end{cases} \\ f_n(x) = ...
12
votes
3answers
8k views

Links between difference and differential equations?

Does there exist any correspondence between difference equations and differential equations? In particular, can one cast some classes of ODEs into difference equations or vice versa?
12
votes
1answer
387 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 = ...