# Tagged Questions

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

77 views

### Recurrence relation solution $a_{n}=\frac{a_{n-1}}{a_{n-1}-a_{n-2}}$

I want to find the analytic form of the recurrence relation $$a_{n}=\frac{a_{n-1}}{a_{n-1}-a_{n-2}},\,a_{1}=2,\,a_{2}=1$$ but when looking at the results they seem chaotic. Is it possible that it ...
24 views

### product of polynomial [on hold]

How can I calculate this? $$\prod_{i=1}^n \left(1+x_i\right)$$ Can I use vieta`s formulas?
40 views

### I need a common term for a recursive sequence

Some days ago, I made a question here about a common term for recursive sequence. I gained very good solutions. Thanks again. Today, I was thinking of a general case which is given below. Assume $p$ ...
209 views

24 views

### Lucas recurrence relation

Lucas recurrence relation is defined as: $V_n = PV_{n-1} – QV_{n-2}$; for $V_0 = 2; V_1 = P$ Here $P$ is positive integer and $Q = {-1, 1}$ or may be $+1$ or $-1$ A Fibonacci Pseudo prime with ...
41 views

### Linear recurrent sequences and matrices.

Let $k$ be a field, let $d$ be an integer greater than $1$, let $(v,x)\in k^d\times k^d$ and let $A\in k^{d\times d}$ be invertible. For all $n\in\mathbb{N}$, let define the following element of $k$:...
336 views

22 views

### Recurrence relations - walk on a graph

given the following undirected graph: I need to find a recurrence relation that describes the number of possible walks starting at point A. Well, naive me Iv'e defined $a_n$ and tried to find ...
23 views

### Simultaneous recurrence relations

Currently working on solving this set of three simultaneous recurrences, but having some trouble. Tried various substitutions, but still cannot seem to make any progress. Also, none of the three ...
39 views

### Deducing Skolem-Mahler-Lech theorem from a $p$-adic interpolation result.

Let $p$ be a prime number, let $d$ be an integer greater than $1$ and let $f\in\mathbb{Z}_p[X_1,\cdots,X_d]^d$. I have already proved the following $p$-adic interpolation theorem: Theorem 1. (...
31 views

### Solving a Linear Recurrence with a Cubic Characteristic Equation

I've been learning Linear Recurrences in my Discrete Math course and I've learned how to solve them when the characteristic equation is a quadratic. Is solving a linear recurrence with a cubic ...
30 views

### Understanding why this simple recurrence relation is structured in this manner

Given this question: Find a recurrence relation for the number of bit strings of length $n$ that contain a pair of consecutive $0$s. And this textbook answer: Let $a_n$ be the number of bit ...
32 views

### Solving linear recurrence after finding values via Quadratic Equation

My HW asks me to solve the following Linear Recurrence: $f(0) = 3$ $f(1) = 1$ $f(n) = 4f(n − 1) + 21f(n − 2)$ Unfortunately my professor ran through the concept of Linear Recurrence ...
41 views

27 views

### Finding a recurrence for number of paths in a certain tree

I have a graph which looks like this: The question is to find a recurrence for $a_n$ - the number of paths of length $n$ that start in vertex $A$. How do you tackle these kind of problems? There is ...
23 views

### Proof that linear difference operator, $(σ-1)^{k+1} (p) = 0$ for all $p$ $\epsilon$ $\mathbb{Q}[t]$, with $deg(p) \leq k$.

I am trying to prove that linear difference operator, $(σ-1)^{k+1} (p) = 0$ for all $p$ $\epsilon$ $\mathbb{Q}[t]$, with $deg(p) \leq k$. In this case $\sigma(t)=t+1$ and $\sigma($anything else$)=$...
30 views

### Proving $J_n(x)N_{n+1}(x)-J_{n+1}(x)N_n(x)=-\dfrac{2}{\pi x}$: Part $3$ of $3$

This is the final part of a calculation that proceeds from this previous question. Here is almost a word for word copy of the textbook question: Use the recursion relations below (for the $N_n(x)$...
33 views

269 views

### How can I find an explicit expression for this recursively defined sequence?

We define the sequence $(u_n)_{n=1}^\infty$by:$$u_{n+1}=1+\frac{1}{u_n}$$ How can I find the limit of this sequence as it goes to infinity? By induction, I can prove that it is bounded above and ...
61 views

### Finding a closed form for $\sum^{n}_{k=1} \frac{k}{(k+1)!}$

I'm finding a closed form to $\sum^{n}_{k=1} \frac{k}{(k+1)!} (n \leq 1)$ (in a environment of induction and recurrence) I've been trying to solve it without success, can anybody help me (?) The ...
21 views

### rearranging a linear first order recurrence

Page 26 of Mathematics for Economics and Finance by M. Anthony and N. Biggs states the following equation, y' = ay' + b, and rearranges it as follows (1 - a)y' = b. I do not understand how the ...
32 views

### Does this family of sequences have the limit $\left(\frac{x^{2p}-y^{2p}}{2p(\ln x-\ln y)} \right)^{1/2p}$ for $p \in \mathbb{R}$?

Define the following family of one parameter sequences: $$a_0=x,~~~b_0=y$$ $$a_{n+1}=\sqrt{a_n \sqrt[p]{\frac{a_n^p+b_n^p}{2}}},~~~b_{n+1}=\sqrt{b_n \sqrt[p]{\frac{a_n^p+b_n^p}{2}}}$$ I conjecture ...
34 views

### Simplifying this series of Laguerre polynomials

I trying to figure out whether a simpler form of this series exists. $$\sum_{i=0}^{n-2}\frac{L_{i+1}(-x)-L_{i}(-x)}{i+2}\left(\sum_{k=0}^{n-2-i} L_k(x)\right)$$ $L_n(x)$ is the $n$th Laguerre ...
73 views

### How do I prove the relationship between $I_n:=\int_{0}^{\pi}(\sin x)^ndx$ and $I_n=\frac{n-1}{n}I_{n-2}$ by partial Integration?

For all $n \in \mathbb{N} : n≥2$, I might add. $$I_n:=\int_{0}^{\pi}(\sin x)^ndx$$ $$I_n=\frac{n-1}{n}I_{n-2}$$ I've tried to rewrite $\int(\sin x)^ndx$ to the form $\int(\sin x)(\sin x)^{n-1}dx$ ...
2k views

### Concrete Mathematics - Towers of Hanoi Recurrence Relation

I've decided to dive in Concrete Mathematics despite only doing a couple of years of undergraduate maths many years ago. I'm looking to work through all the material whilst plugging gaps in my ...
1k views

### Concrete Mathematics - The Josephus Problem

I've been going through Concrete Mathematics and have a question on the inductive proof for the Josephus problem. Recurrent relation: $J(1) = 1$ $J(2n) = 2J(n) - 1$ $J(2n+1) = 2J(n) + 1$...
459 views

### Convergence of sequence: $\sqrt{2} \sqrt{2 - \sqrt{2}} \sqrt{2 - \sqrt{2 - \sqrt{2}}} \sqrt{2 - \sqrt{2 - \sqrt{2-\sqrt{2}}}} \cdots$ =?

In other words, if we define a sequence $$\displaystyle a_{n+1} = \sqrt{2-a_n}, \,\,\,a_0 = 0 .$$ Then, we need to find $$\displaystyle \prod_{n=1}^{\infty}{a_n}.$$ Well, from here I don't seem ...
31 views

### How do I compute the generating function for this number sequence?

I am trying to compute the generating function for the number sequence given by $a_n = (-1)^n$. I know that the solution is $A(x) = \frac{1}{1+x}$ but when I try to solve it using the procedure of ...
67 views

### Iterating a multiple of sine function makes a square wave

So, I found something curious playing around with a graphing calculator. Say we start with a function, $f_1(x) = 2\sin(x)$ and we define a constant, $C$,to be the positive fixed point for $f_1(x)$. ...
Given recurrence $$T(n) = 3T(n/2) + O(n)$$ $$let\:cn >= O(n)$$ for some constant c I can bound $$T(n)$$ in terms of $$T(n/2)$$ so I have $$T(n) <= 3T(n/2)+cn, \ \ \ \ \ k = 1 \ call$$ So I ...