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

learn more… | top users | synonyms (2)

1
vote
0answers
42 views

Complex numbers product and ratio, prove this relation.

Define a table $T$ as follows: $$\text{If}\; n\geq k \; \text{then} \; T(n,k) = (2+3 i) \sum _{i=1}^{n-1} T(n-i,k-1)+(5+7 i) \sum _{i=1}^{n-1} T(n-i,k) \; \text{else} \; T(n,k) = 0$$ Then take rows ...
0
votes
0answers
43 views

Concrete math generalized josephus recursion understanding 1.15

I am studying through the josephus problem in concrete math , Here is the equation of binary form $$f(1) = α ;$$ $$f(2n + j) = 2f(n) + β_j ,$$ $$\text{ for } j = 0, 1 \text{ and } n \geq 1$$ this ...
1
vote
3answers
49 views

Why, intuitively, does the solution to a general linear recurrence relation make sense?

I reasoned through the solution to a differential equation, and $e^{\alpha x}$, for better or worse, seems to make sense. Each derivative sending the function to itself seems to suggest $e^{\alpha ...
4
votes
1answer
100 views

Does this sequence consist of squares of integers?

Question: let sequence $\{x_{n}\}$ such $$x_{0}=0,x_{1}=1,x_{2}=0,x_{3}=1$$ and such $$x_{n+3}=\dfrac{(n^2+n+1)(n+1)}{n}x_{n+2}+(n^2+n+1)x_{n+1}-\dfrac{n+1}{n}x_{n}$$ show that:$ ...
1
vote
1answer
45 views

Evaluation of a Hankel-like determinant

I consider the following determinant (Hankel-like?) $$ [f_1,f_2,...,f_n]:=\begin{vmatrix} f_1 & f_2 & \cdots & f_{n-1} & f_n\\ n-1 & f_1 & \cdots & f_{n-2}& f_{n-1}\\ 0 ...
3
votes
1answer
59 views

Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$ \begin{array}{cccccccccc} 1 & = & ...
6
votes
2answers
139 views

Finding non-negative integers $m$ such that $(1 + \sqrt{-2})^m$ has real part $\pm 1$.

I believe that the integers $m$ with $(1+\sqrt{-2})^m$ having real part $\pm 1$ are $0, 1, 2$ and $5$, but I'm having trouble proving it. Write $$a_m = \Re((1+\sqrt{-2})^m) = \frac{(1 + \sqrt{-2})^m ...
0
votes
1answer
34 views

Prove that the elements of these two sequences are not null

Let $x_{n+1}=x_n+2y_n$ and $y_{n+1}=y_n-x_n$, where $x_1=1$ and $y_1=-1$. I tried proving by contradiction, I tried by induction, I got nothing. This is a question I had on an exam, I didn't manage ...
1
vote
1answer
36 views

Recurrence relation and combinatorics

I am reading p.4 of the article http://mercercountymathcircle.files.wordpress.com/2014/03/recurrence_relations.pdf which consider the following problem: Find the units digit of ...
2
votes
0answers
63 views

Boundedness of solutions of Difference equation

Consider a second order difference equation in complex plane, \begin{equation} z_{n+1}=\frac{\alpha + \beta z_{n}}{1+z_{n-1}},\qquad n=0,1,\ldots \end{equation} where the parameters $\alpha, ~\beta$ ...
1
vote
3answers
346 views

Homework - Resolve the recurrence relation

What's the closed formula of this recurrence relation? $$a_n = a_{n-1}+2a_{n-2}+2^n \text{ with } a_0=1, a_1=2 $$
4
votes
0answers
82 views

How to solve a non-homogeneous second-order linear difference equation with both a forward and a backward difference?

Quite a long title for this: I'm looking for the general solution of the following difference equation: $$ax_{t+1} -bx_t + x_{t-1} = c + u_t$$ where $a,b,c$ are real constants and $u_t$ is a bounded ...
1
vote
0answers
33 views

Possible to determine if a more 'compact' solution to a linear recurrence exists?

Given a linear a recurrence relation. It is possible to express a solution in terms of summations, products, and the coefficients which appear in the recurrence. For example, in the case of a single ...
0
votes
0answers
22 views

Comparing Generalized Continued Fractions

Gosper lays out a method (under Approximations) for comparing regular (a.k.a simple) continued fractions which have all partial numerators set to 1. Continue comparing terms until they differ, then ...
3
votes
1answer
216 views

How to solve this recurrence Relation - Varying Coefficient

Sir,I have two questions related to this recurrence relation. It has been messing with me for long. Because of this I couldn't proceed my work for some time .This contains a polynomial term n+2 in ...
0
votes
1answer
76 views

Solving this recurrence relation

please tell me a way to solve this recurrence $$n\cdot R_n=C_1\cdot R_{n-1}+C_2\cdot R_{n-2}.$$ $C_1$ and $C_2$ are constants.. There is an $n$ there in the left hand side.. it makes mess. I tried ...
0
votes
0answers
61 views

solution of a recurence equation

The equation is $f(n)=\left(1+\frac{na}{b}\right)f(n-1)-\frac{na}{b}f(n-2)-\frac{n}{b}$ where $a,b>0$ and real, and $f(0)=0$, $f(1)=c\in R$. I expressed $f(2)$, $f(3)$, $f(4)$ and $f(5)$ in ...
3
votes
1answer
41 views

Newton Rhapson Algorithm Accuracy

I read somewhere that the NR algorithm in general (given an appropriate initial value) increases in accuracy by roughly two decimal places per iteration. Is this something that can be proven, or is ...
6
votes
0answers
97 views

Nonlinear inhomogeneous recurrence $f(x)^2=f(x+1)+S(x)$ to find nested radical

I want to solve the recurrence relation $$f(x)^2=f(x+1)+S(x)$$ where $S(x)$ is a given polynomial. The background is to find nested radicals expressions of the form ...
4
votes
1answer
110 views

Going from closed form to recurrence relation

If I had a closed form for a sequence that I suspect to represents a recurrence relation how would I determine the recurrence relation? In particular, I have the sequence $$a_n = ...
0
votes
1answer
41 views

Recursive Relationship: Paper Towels

A standard roll of paper towels consists of a cardboard tube with outer diameter $4$ cm. Imagine the paper being wound onto the cardboard tube. After each complete winding, the total diameter of the ...
9
votes
8answers
273 views

Proof that if $a_1=1$ and $a_{n+1}=1+\frac{1}{1+a_n}$

Question: Proof that if $$a_n=\left\{ \begin{array}{ll} a_1=1\\ a_{n+1}=1+\frac{1}{1+a_n} \end{array} \right.$$ then $a_n$ converge, and then find $\lim_{n \to \infty}a_n$. I found ...
25
votes
3answers
537 views

Finding every $n$ such that $a_n$ is an integer

Let us define $\{a_n\}$ as $a_1=a_2=1$,$$a_{n+2}=a_{n+1}+\frac{a_n}{2}\ \ (n=1,2,\cdots).$$ Then, is the following conjecture true? A conjecture : If $a_n$ is an integer, then $n\le 8$. I ...
3
votes
2answers
50 views

recurrent events-Probability of even number of successes

Let E be the event of an even number of successes. $u_n$:Probability of E occurring at the nth trial not necessarily for the first time $f_n$:Probability of E occurring at the nth trial for the first ...
0
votes
0answers
28 views

Produce a list of the most-similar units, given various correlations/relationships

I have a database full of units (U1 - U50, U51...) where every unit has the same standard attributes (A1 - A10) and where a % of each attribute defines the amount of that attribute for that particular ...
1
vote
0answers
45 views

General Solution to Linear Difference Equation: Is this correct

Notation: Let $$Q_1[f(x)] = \lim _{h \rightarrow 1} \frac{f(x + h) - f(x) }{h}$$ And let $$Q_1^{-1}\left[f(x)\right] = G(x)|Q_1\left[g(x)\right] = f(x)$$ Consider the equation $$a_0(x) + ...
2
votes
1answer
58 views

Filling of a tank - recurrence relation

Suppose a tank has a maximum limit of 100 units. Each day 2,1 and 0 units are added to the water level with probability p,r and q. Any excess water would overflow and if it reaches the minimum level ...
14
votes
4answers
405 views

Converting recursive equations into matrices

How do we convert recursive equations into matrix forms? For instance, consider this recursive equation(Fibonacci Series): $$F_n = F_{n-1} + F_{n-2}$$ And it comes out to be that the following that ...
3
votes
2answers
193 views

Recurrence Master Theorem Question with asymptotic Upper and Lower Bounds

If I were to solve the recurrence of following equation and give asymptotic upper and lower bounds: $$T(n) = 4T(\frac{n}{2}) + n^2 + n$$ Can I apply Master Theorem on this? My attempt was following: ...
1
vote
1answer
45 views

Queuing theory-Multiple server (reducing simple recurrence formulas)

The equations given in 6.3 have been reduced which really eases the computation in further studies. But I tried to find the method of reducing these but I could not find a way at all. Any hints will ...
2
votes
2answers
79 views

Finding a Closed Form for a Recurrence Relation

I know that a general technique for finding a closed formula for a recurrence relation would be to set them as coefficients of a power series (i.e. a generating function). Then use properties of ...
1
vote
1answer
31 views

non-homogenous recurrence relation, with split boundary conditions

I have non-homogenous recurrence relation: $x_{t+1}=\alpha x_t+\beta x_{t-1}+\gamma$ with the following boundary conditions: $x_2=\alpha x_1+\gamma$ $x_{T}=1/2x_{T-1} +1/2$ Anyone know how to ...
3
votes
1answer
39 views

What's the time complexity of T(n)=nlogn+T(n-1)?

The title says it all. The best I can come up with is that this expands to T(0) + 1log 1 + 2log 2 + ... + (n-1)log (n - 1) + nlog n which is ...
3
votes
1answer
82 views

Limit of a recursiv trigonometric function

So while doing my math homework I recently stumbled upon this little thing: It seems that $y_n = \sin(y_{n-1}) + k$ with arbitrary $y_0$ and $k$ converges to a definite value for $n \to \infty $. ...
0
votes
0answers
58 views

How can I cleverly use the reverse triangle inequality in this case?

Say, we have the following recurrence relation: $$x_{k+2}=4x_{k+1}+x_k(-3-2h\lambda)$$ with $x_0 $ given, $x_1=(1+h\lambda)x_0, h$ small (step size), and $\lambda<0$. Here is the context is case ...
1
vote
1answer
72 views

Fibonacci numbers $F_{n+3} + F_{n} = 2F_{n+2}$

Prove $F_{n+3} + F_{n} = 2F_{n+2}$ for any positive integer n. So What I did was this: fn+ fn+1 = fn+2 fn + fn+1 = fn+2 => fn+2 -fn+1 fn+1 + fn+2 = fn+3 then I subsituted into equation in ...
3
votes
1answer
79 views

Help finding the closed formula for a recurrent relation

In the last steps of finding the complete solution of a linear differential equation by a power series, I got stuck on finding the closed formula for the following recurrent relation: $$B_n = B_{n-1} ...
1
vote
0answers
74 views

Need help with these recurrence relations

I had received some challenging recurrence last week, I did most of them except this and also one of its kind. It states Given $a_0=0$ and $a_1=1$, solve these recurrence relations: ...
3
votes
1answer
130 views

General Solution of Functional Equation

What is the general solution to: $$ \frac{f(x+h)-f(x)}{h} = \frac{1}{x} \tag{1} $$ Obviously the solution to this for the limiting case of $h\to 0$ is $f(x) = \ln(x) + c$ Attempting to solve the ...
1
vote
2answers
47 views

Generating function satisfying a second degree equation

I got this problem in an exercise list: Let $G(x)$ be the generating function of the numeric sequence $(C_n; n \geq 0)$ satisfying the recurrence equation: $$C_n = \sum_{k=0}^{n-1}C_kC_{n-k-1}, ...
2
votes
1answer
75 views

a system of finite difference equations

Let $a,b>0$ such that $ab<1$ consider the system$$x_{t+1}=x_ty_t+ay_t$$ $$y_{t+1}=x_ty_t+bx_t$$ I would like you to help me answer the following: find values $a$ and $b$ ​​for which the ...
0
votes
1answer
44 views

Limit of recurrence relation $x_k= f(x_{k-1})$ for an increasing function $f:[0,1]\to[0,1]$

Is there a standard result out there that gives the following? It looks graphically like it must be true, but I'd like to appeal to a known result if possible. Let $f:[0,1]\to[0,1]$ be a continuous, ...
2
votes
1answer
76 views

Quadradic recurrence relation

There is an method to solve recurrences of the form $a_{n+1} = (a_n + c)^2$? I am particularly interested when $c = 1$. I tried to use generating functions but I got stuck with. Let $G(x) = \sum_{k ...
3
votes
1answer
90 views

Solving a recurrence relation ${}$

I feel I'm wasting my time trying to solve this $a_0$ is given $\displaystyle a_{n+1}=\frac{n-1}{n+2}(a_n-n-2)$ Mathematica found a closed form but there's a problem when evaluating for ...
3
votes
2answers
111 views

Determinant involving recurrence

Evaluate $$\left| A \right| = \left| {\matrix{ {x + y} & {xy} & 0 & \cdots & \cdots & 0 \cr 1 & {x + y} & {xy} & \cdots & \cdots & 0 \cr 0 ...
1
vote
1answer
89 views

Divide and Conquer (recurrence relation problem)…

The problem: (a) Use a divide-and-conquer approach to devise a procedure to find the largest and next-to-largest numbers in a set of n distinct integers. (b) Give a recurrence relation for ...
0
votes
1answer
31 views

Change of variables in function $T(n)$.

I've been given this recurrence to solve: $T(n) = T(\sqrt n) + \theta(lglgn)$ And I'm told that the way to solve it is to let $m = lgn$, so that the recurrence can be rewritten as follows: $S(m) = ...
1
vote
0answers
16 views

Literature on functional difference equations

dear community. I'm looking for books/guides on functional difference equations. Can you recommend some? Below I try to explain what kind of equations I have in mind. As an example, one of the ...
6
votes
1answer
129 views

Limit related to the recursion $a_{n+1}=(1-n^{-1/4}a_n)a_n$

Let $0<a_{1}<1$, with $$a_{n+1}=a_{n}(1-n^{-\frac{1}{4}}a_{n})$$ Does there a real numbers $A$ which make the limit $$ ...
0
votes
3answers
54 views

Recurrence relations for students of the third year of secondary school.

I am not able to solve this problem in order to find a explicit form for the recurrence relation (note: in the original text I can read "a with n" and "a with n-1", but I am not able to format here) ...