# Tagged Questions

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

321 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 ...
307 views

### Common terms in general Fibonacci sequences

Mathworld notes that "The Fibonacci and Lucas numbers have no common terms except 1 and 3," where the Fibonacci and Lucas numbers are defined by the recurrence relation $a_n=a_{n-1}+a_{n-2}$. For ...
44 views

### prove the sequence is increasing

Im asked to show the sequence $a_{n+1}=\sqrt{3+2a_{n}}$ where $a_{1}=0, a_{2}=1$ is increasing and bounded and therefore convergent. I don't even know how to start the proof. Im sure it increases ...
245 views

73 views

### Repeatedly taking mean values of non-empty subsets of a set: $2,\,3,\,5,\,15,\,875,\,…$

Consider the following iterative process. We start with a 2-element set $S_0=\{0,1\}$. At $n^{\text{th}}$ step $(n\ge1)$ we take all non-empty subsets of $S_{n-1}$, then for each subset compute the ...
50 views

### Recurrence $u_{n+1}u_{n-1}-u_n^2=Ar^{n-1}$

I was going through some old puzzles and encountered one where there was a non-linear recurrence of form $$u_{n+1}u_{n-1}-u_n^2=Ar^{n-1}$$ with $u_0$ and $u_1$ given. I know I can use a test form ...
2k views

71 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 ...
178 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 ...
160 views

### Another recurrence… $T(n)=\sqrt{2n} \cdot T(\sqrt{2n}) + \sqrt{n}$

I'm trying to solve the following recurrence : $$T(n)=\sqrt{2n}\cdot T(\sqrt{2n}) + \sqrt{n}$$ I've tried substituting $n$ for some other variables to transform the above to something easier without ...
107 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 ...
1k 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 ...
474 views

### How to solve this recurrence $K(n)=2K(n-1)-K(n-2)+C$?

The recurrence is $K(n)=2K(n-1)-K(n-2)+C$ where $C$ is a constant. What I have tried is substituting $2K(n-1)$ as we do in fibonnacical recurrences. It didn't gave me a fruitful expression! Can ...
2k views

### How to find $\lim a_n$ if $a_{n+1}=a_n+\frac{a_n-1}{n^2-1}$ for every $n\ge2$

$a_n$ is a sequence where $a_1=0$ and $a_2=100$, and for $n \geq 2$: $$a_{n+1}=a_n+\frac{a_n-1}{(n)^2-1}$$ I have a basic understanding of sequences. I wasn't sure how to deal with this recurrence ...
2k views

209 views

### How to solve this recurrence relation $a_{n+2} = \sqrt{a_{n+1}\cdot a_{n}}$?

I am trying to solve the recurrence: $$a_{n+2} = \sqrt{a_{n+1}\cdot a_{n}}$$ but here is a problem for me. After few steps I have this: $$a_n^2 = a_{n-1}\cdot a_{n-2}$$ and I don't now what to do ...
159 views

### $x_{n+1} = \sqrt{3x_n}$ converges for $x_1 = 1,x_1 = 27$ Proof

Prove $x_{n+1} = \sqrt{3x_n}$ converges for $x_1 = 1,x_1 = 27$. (Separate problems for $x_1 = 1$ and $x_1 = 27$.) EDIT: Took out bad algebra.
170 views

### Convergence of a recurrence

Given the recursive definition (starting with a positive integer) $$a_n = \frac{a_{n-1}}{2}+4$$ I am trying to find an explicit form and show that it approaches 8. So I started by writing it out, ...
93 views

### Please solve this recurrence relation question for $8a_na_{n+1}-16a_{n+1}+2a_n+5=0$

Suppose $a_1=1$ and $$8a_na_{n+1}-16a_{n+1}+2a_n+5=0,\forall n\geq1,$$Please help to sort out the general form of $a_n$. Here are the first a few values of the series. Not sure if they are useful as ...
285 views