# Tagged Questions

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

2k views

691 views

959 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 $$S(x)-S(x^{2})=x$$ ...
810 views

837 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 ...
490 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 ...
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 ...
493 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. ...
447 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 ...
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: ...
2k views

300 views

914 views

### How does one solve this recurrence relation? [closed]

We have the following recursive system: $$\begin{cases} & a_{n+1}=-2a_n -4b_n\\ & b_{n+1}=4a_n +6b_n\\ & a_0=1, b_0=0 \end{cases}$$ and the 2005 mid-exam wants me to calculate answer ...
978 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 ...
344 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 ...
271 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 ...
589 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 ...
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 ...
474 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 Solutions....
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 ...
### 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 ...