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

learn more… | top users | synonyms (2)

3
votes
3answers
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 ...
0
votes
0answers
25 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?
2
votes
1answer
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$ ...
17
votes
2answers
210 views

Fibonorial of a fractional or complex argument

Let $F(n)$ denote the $n^{\text{th}}$ Fibonacci number$^{[1]}$$\!^{[2]}$$\!^{[3]}$. The Fibonacci numbers have a natural generalization to an analytic function of a complex argument: $$F(z)=\left(\phi^...
0
votes
0answers
47 views

Exam Recurrence and Complexity [on hold]

I have an exam coming up in a few days and my prof gave us a couple questions we should know as he will make new questions based on these topics the explanations must be in-depth because it will be a ...
1
vote
5answers
51 views

Solving $a_n = a_{n-1} + 7n$ for $n\ge1$ and $a_0 = 4$

First, I found the homogeneous solution: $$r^n - r^{n-1} = 0$$ $$\Rightarrow r = 1$$ So the homogeneous solution is of the form: $$c(1)^n = c$$ Then, to find a particular solution, I "guessed" the ...
0
votes
1answer
23 views

Linear combination of sequence related to Fibonacci

Let $a= \frac{1+\sqrt{5}}{2}$ and $b= \frac{1-\sqrt{5}}{2}$. Prove that for all $c,d \in \mathbb{N}$ that $g_n = ca^n + db^n$ satisfies $g_{n+2} = g_{n+1} + g_{n}$ for all $n\in \mathbb{N}$. I'm ...
0
votes
1answer
31 views

First Order Difference Equations - Using Eigenvectors/Values

I was reading some notes and there was the following section: Start with a given vector $\vec{u}_0$. We can create a sequence of vectors in which each new vector is $A$ times the previous vector: $$\...
1
vote
0answers
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 ...
0
votes
1answer
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$:...
7
votes
3answers
337 views

How can I rewrite recursive function as single formula?

There is following recursive function $$ \begin{equation} a_n= \begin{cases} -1, & \text{if}\ n = 0 \\ 1, & \text{if}\ n = 1\\ 10a_{n-1}-21a_{n-2}, & \text{if}\ ...
0
votes
0answers
36 views

Two variable recurrence relations with conditionals

Is it possible to obtain a generating function for the sequence described by the following recurrence? $$ f(n,m) = \begin{cases} f(n, \thinspace m-1) + f(n-m, \thinspace m-1), & \text{ if } n \...
0
votes
2answers
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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. (...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
3
votes
2answers
41 views

Estimate growth of a recurrence convolution

Consider the following recurrence relation $$ a_{m+1} = (4 m + 1) \sum_{k=1}^m a_k a_{m-k+1}, \qquad a_1 = 1. $$ The first several values are $$ a_1 = 1,\; a_2 = 5,\; a_3 = 90, \; a_4 = 2665, \; a_5 = ...
-3
votes
0answers
65 views

Nonlinear recurrence equation $x\to(b/x)+c$ [closed]

I have problem for solving this nonlinear recurrence equation: x_{i}=(b/x_{i-1})+c b,c are constant x_{1}=1
0
votes
3answers
71 views

Very confused by recurrence relations as a concept

We've been introduced to recurrence relations as a concept in my Discrete class. One question asks: Given the recurrence: $S(1) = 1$, $S(n) = 2S(n − 1) + 3 (for \ n > 1)$ prove ...
5
votes
2answers
788 views

How to find recurrence relation of a given solution.

Determine values of the constants $A$ and $B$ such that $a_n=An+B$ is a solution of the recurrence relation $a_n=2a_{n-1}+n+5$. I know that the characteristic equation is $r-2 = 0$ which has the root ...
1
vote
1answer
46 views

derivation of fibonacci log(n) time sequence

I was trying to derive following equation to compute the nth fibonacci number in O(log(n)) time. F(2n) = (2*F(n-1) + F(n)) * F(n) which i found on wiki form the ...
0
votes
0answers
11 views

How can I find runtime bounds for this recursive sum?

As part of a larger homework task, I'm investigating the following equation, given that $1 \leq s \leq n \in \mathbb{N}$ and $T_n(0) = 0$. $$ T_n(s) = \frac{1}{\lfloor \log s \rfloor} [ 1 + \log n + ...
2
votes
1answer
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 ...
0
votes
1answer
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$)=$...
0
votes
0answers
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)$...
1
vote
0answers
33 views

Closed form expression for a two variable recursive relation

Let $F(m,n)$ be defined recursively for non-negative integers $m$ and $n$ according to the following rules: $F(0,n) = 0$ for all $n$, $F(m,n) = F(n,m)$ for all $m$ and $n$, and if $n\ge m$, then $F(...
11
votes
4answers
787 views

How to find explicit formula for two recursions?

I have to find explicit solution for two intertwining recursions $$\begin{align} f(n)&=f(n-2)+2g(n-1) \\ g(n)&=g(n-2)+f(n-1) \end{align}$$ for $f(0)=1, f(1)=0, g(0)=0 ,g(1)=1$. What ...
-1
votes
2answers
26 views

Closed form for a certain recurrence relation

Can anybody give me a closed form for the (limit of the) recurrence relation $a_0 = 0$, $a_{n+1} = \frac12\cdot\big(1 + a_n^2\big)$? And more general: Can anybody give me a closed form for the (limit ...
7
votes
4answers
313 views

Limit of $x_n^3/n^2$ when $x_{n+1}=x_n+ 1/\sqrt {x_n}$ with $x_0 \gt 0$

Let $(x_n)_{n \ge 0}$ a sequence of real numbers with $x_0 \gt 0$ and $x_{n+1}=x_n+ \frac {1}{\sqrt {x_n}}$. Check the existence and find $$L=\lim_{n \rightarrow \infty} \frac {x_n^3} {n^2}$$ ...
0
votes
1answer
46 views

Does the explicit formula for recurrence relation exist

Does an explicit formula exist for this recurrence relation? If so, what is it? $ f(0) = 1 $ $ f(n) = \frac{n}{f(n-1)} $
3
votes
2answers
54 views

Prove that $\Gamma(-k+\frac{1}{2})=\frac{(-1)^k 2^k}{1\cdot 3\cdot 5\cdots(2k-1)}\sqrt{\pi}$.

I was able to prove that $$ \Gamma\left (k+\frac{1}{2} \right )=\frac{1\cdot 3\cdot 5\cdots(2k-1)}{2^k}\sqrt{\pi}.\tag{$k\geq 1$}$$ using the Legendre's duplication formula. But I can't do the same to ...
1
vote
1answer
24 views

# of bit strings of length n (even>2), with n/2-1 zeros and n/2+1 ones, zero followed by one

case 1: What is the number of bit strings of length 4, with 1 zero and 3 ones, zero must be followed by one Answer: 3 case 2: What is the number of bit strings of length 6, with 2 zeros and 4 ones, ...
0
votes
0answers
40 views

Solution to a first order linear difference equation

The two questions are with respect to the following first order linear difference equation $(Y_{t} - Y_{t-1}) = (1-\lambda) (X_{t-1} - Y_{t-1})$, for $t \geq n$ Also, note that the process ...
2
votes
1answer
51 views

First-Order Linear Difference Equation with Constraint

Consider the following first order linear difference equation for $y$: $$y_{t+1} = \alpha * y_{t} + \beta * x_{t-n+1} ~~\forall t \ge n$$ For initial conditions, one could assume that $x_{i} ...
7
votes
3answers
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 ...
1
vote
3answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
1
vote
2answers
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$ ...
6
votes
1answer
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 ...
3
votes
1answer
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$...
27
votes
2answers
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 ...
1
vote
2answers
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 ...
6
votes
1answer
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)$. ...
1
vote
1answer
402 views

Help Solve Recurrence Relation T(n) = 3T(n/2) + O(n)

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 ...
1
vote
0answers
23 views

Prove using induction that $C(n) = C(n/5) + C(3n/4) + n$ is $O(n)$

I was hoping someone could take a look at my answer to this question and check if it's correct and offer some advice/help on how to correct if it's wrong. Question: Consider the function $C: \mathbb ...