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

learn more… | top users | synonyms

1
vote
1answer
42 views

Find all solutions of the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2} + 2^n + 3n$

Question: Find all solutions of the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2} + 2^n + 3n$ (Hint: Look for a particular solution of the form $qn2^n + p_1n + p_2$, where $q, p_1, p_2$ are ...
0
votes
0answers
17 views

Solving a simple Recurrence in summation form(very special case)

I have a bit confusing recursion form $\sum_{n=2}^{\infty}\{f(n)\frac{n}{n-1}\}=C, \tag 1$ $f(0)=b,f(1)= a,f(2)=c$ and $C$ are constants. Could you help me to solve this recursion or help me to ...
0
votes
0answers
15 views

Recurrence relation-Summation of a series [on hold]

Sir, I have a Converging recurrence relation given as below, $-(\psi(n-1)) ...
0
votes
0answers
27 views

Equality of a recurrent sequence and of a running maximum of another sequence

Let $\{a_n\}$ be a sequence of real numbers. Let $c,b$ be real constants. Define $$ L_{k,n}=\exp\left\{c\sum_{i=k}^n(a_i+b)\right\}. $$ Then it can be shown that $L_n=\max_{1\le k\le n}L_{k,n}$ is ...
4
votes
1answer
38 views

Is it possible to calculate the roots of the difference between successive terms of this polynomial series $\rm{P}_n (x)=x\rm{P}_{n-1}-r\rm{P}_{n-2}$

Consider the polynomial series defined by the following recursion formula: $$ \begin{align} &\mathrm{P}_0 = 1 \\ &\mathrm{P}_1 = x-r \\ &\mathrm{P}_n = x\mathrm{P}_{n-1} - ...
5
votes
0answers
52 views

Sum of infinite series defined recursively

Suppose $s$, $t$, and $\delta$ are constants satisfying $0<s<t<1$ and $\delta>1$. An infinite sequence $\{y_k\}_{k=1}^{\infty}$ defined as follows: The initial term, $y_1$, is the ...
-1
votes
1answer
41 views

Savings after $n$ years (using recurrence) [on hold]

A person deposits Rs. $250, 000/$ in a bank in a saving bank account at a rate of $8 \%$ per annum. Let $P_n$ be the amount payable after $n$ years, set up a recurrence relation to model the problem. ...
6
votes
3answers
199 views

Solving recurrence relation: Product form

Please help in finding the solution of this recursion. $$f(n)=\frac{f(n-1) \cdot f(n-2)}{n},$$ where $ f(1)=1$ and $f(2)=2$.
-1
votes
1answer
37 views

Initial values are lost (diff eq to Transfer function)?

I read eternal Julius O. Smith III and he says that $$x_{n-m} = z^{-m}X(z)$$ Particularly, difference relation $$y_{n} = y_{n-1} + x_{n}$$ is solved by by $$Y = z^{-1}Y + X = {X \over ...
1
vote
0answers
24 views

Question about finite sums and integer recursions.

Let $n$ be a positive integer and let $g(n)$ be a given strictly increasing integer function such that $0<g(n)<n$ for all $n$. Also the sequence $ |g(n) - n|$ is unbounded as $n$ grows. Let ...
0
votes
0answers
32 views

Why does s = z+1?

What exactly is Laplace transform? motivated me to ask why unit function is 1/s by Laplace transform and 1/(1-z) by Z-transform? Both seem to be integrals of delta-pulse and secondary integration ...
3
votes
4answers
59 views

Elementary Proof of sum of alternating factorials

so I came across the rather interesting identity $$ \sum_{i = 0}^{\infty}\left[\sum_{j=0}^{i}\left[\frac{(-1)^j}{j!} \right] \prod_{j=0}^{i}\left[ (x-j)\right] \right] = x! $$ For positive integers ...
4
votes
1answer
62 views

Expressing a Recursion in terms of factorials

Given the recursion $$f(n) = nf(n-1) + (n-1)f(n-2) $$ $$f(0) = 1, f(1) = 1$$ How exactly does one express the target function? I know that $$f(n) = nf(n-1)$$ gives rise to $$f(n) = \Gamma(n+1)$$ ...
11
votes
3answers
244 views

Difficult Recurrence

I am trying to solve a Sangaku problem. The blue circles have radii one. The goal is to find the total area of all the other circles (the three sequences of circles repeat ad infinitum). I have ...
1
vote
1answer
23 views

Is it possible that a randomized recursion has a nonzero probability of either converging or diverging?

I have very little "hands-on" experience with probability, but here is my context: I was looking at the random Fibonacci sequence: $$f_0=f_1=1, f_n=f_{n-1}+Xf_{n-2}$$ where $X$ is chosen randomly ...
1
vote
0answers
25 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
18 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
37 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
95 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
33 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
48 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
106 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
24 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 ...
1
vote
3answers
297 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
32 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
26 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
14 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 ...
0
votes
1answer
60 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
58 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
30 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
85 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
93 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
35 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
256 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 ...
27
votes
3answers
498 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 true? If $a_n$ is an integer, then $n\le 8$. I conjectured this by using ...
3
votes
2answers
46 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
20 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
39 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
54 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 ...
12
votes
4answers
342 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
53 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
17 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
65 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
0answers
18 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
37 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
72 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
44 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
67 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
70 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} ...