# Tagged Questions

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

4answers
116 views

### Solution verification: Prove by induction that $a_1 = \sqrt{2} , a_{n+1} = \sqrt{2 + a_n}$ is increasing and bounded by $2$

I have the following recursive relation (sequence): \begin{align} a_1 = \sqrt{2}, \quad a_{n+1} = \sqrt{2 + a_n} \end{align} My Try: I'm a little skeptical of my manipulations near the end but it ...
0answers
63 views

### Generating function for recurrence in two variables

Given characteristic polynomial for the recurrence in two variables (say $F(x,y)$) $$(y^2-1)^x$$ and initial values can generating function for $F(x,y)$ be derived? I know how to do it for a ...
1answer
64 views

### Solve this recurrence relation

Solve the following recursions: $a_{n+1}=3a_n-a_{n-1}-1$ and $a_{n+1}=4a_n-a_{n-1}-1$. (These are to be solved separately, not simultaneously) I tried using generating functions but it got messy. Any ...
1answer
86 views

3answers
114 views

### Use the generating function to solve a recurrence relation

We have the recurrence relation $\displaystyle a_n = a_{n-1} + 2(n-1)$ for $n \geq 2$, with $a_1 = 2$. Now I have to show that $\displaystyle a_n = n^2 - n +2$, with $n \geq 1$ using the generating ...
1answer
31 views

### For a solution of linear recurrence relation, $\lim_{n\to\infty}a_n^{1/n}$ is a zero of a related polynomial

On page 134 of J.H. van Lint's book A Course in Combinatorics, it says from $a_n=5a_{n-1}-7a_{n-2}+4a_{n-3}$ $(n\ge5)$, we find that $\lim_{n\to\infty}a_n^{1/n}=\theta$, where $\theta$ is the ...
1answer
69 views

0answers
128 views

### An Impossible Sequence of Prime Powers

Let $x_1,x_2,\ldots$ be a sequence of positive integers that satisfies the recurrence relation $$x_{n+1}=2x_n(x_n-1)+1$$ for all positive integers $n$. It seems impossible that every term in this ...
1answer
38 views

### Tools for solving recurrent expresions

I've got a problem involving a recurrent expression. I would like to find a solution of $x_t$ that let me take derivatives or finding the minimum of the function. Does anybody know tools for solving ...
1answer
46 views

1answer
133 views

### How do I prove that the recurrence contains no perfect square?

Given the recurrence $$a_{n+2} = 14a_{n+1} - a_n - 6$$ with $a_1=1$ and $a_2=8$, how do I prove that none of the $a_n$'s apart from $a_1$ is a perfect square. This is not a homework problem, rather ...
1answer
359 views

### Variation of Tower of Hanoi

I have been reviewing the solution of the following problem for which I have to find a recurrence relation for the number of moves: "In the Tower of Hanoi puzzle, suppose our goal is to transfer all ...
2answers
132 views

### Solving recurrences whose characteristic equations have complex roots

In my Discrete Mathematics lecture notes, there is a section regarding solutions for linear recurrences whose characteristic polynomials have complex roots. There is a particular statement which I am ...
0answers
23 views

3answers
127 views

1answer
30 views

### Recurrence in Kepler's Equation (trascendent equation)

Kepler's equation is $E-e\sin E = M$, where $e,M$ are constants. My teacher of celestial mechanics told me that if $e\ll 1$, I should take a first aproximation $E_1=M$, then a second aproximation \$...