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

learn more… | top users | synonyms

26
votes
3answers
345 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 ...
9
votes
7answers
129 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 ...
0
votes
1answer
20 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 ...
7
votes
3answers
2k views

Why is solving non-linear recurrence relations “hopeless”?

I came across a non-linear recurrence relation I want to solve, and most of the places I look for help will say things like "it's hopeless to solve non-linear recurrence relations in general." Is ...
0
votes
0answers
32 views

Did I obtain this recursion in the Fourier domain correctly?

I would like to calculate the following recursion: $$f_n(x)=\int_{B}^{A}f_{n-1}(x-\omega)f(\omega)\mbox{d}\omega\quad\quad f_1(\omega):=f(\omega)$$ This is simply the convolution of $f$ with itself ...
2
votes
2answers
39 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 ...
2
votes
1answer
52 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 ...
4
votes
4answers
355 views

How do I resolve a recurrence relation when the characteristic equation has fewer roots than terms?

I know how to solve "simple" recurrence relations. For instance, say you have: $$c_0 = 20$$ $$c_1 = 30$$ $$c_n = 3 c_{n-1} - 2 c_{n-2}$$ We can write the characteristic equation as: $$3x^{n-1} - ...
0
votes
0answers
10 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
38 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) + ...
10
votes
4answers
329 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 ...
2
votes
2answers
43 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
0answers
11 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
57 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 ...
5
votes
0answers
73 views

Is this a recurrence for the characteristic sequence of composite numbers?

The characteristic sequence of composite numbers is equal to 1 if $n$ is not a prime number and equal to 0 if $n$ is a prime number, starting: $$1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1,...$$ where the ...
1
vote
0answers
16 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
36 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
61 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
43 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
63 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
69 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
67 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
102 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
37 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}, ...
0
votes
0answers
30 views

Standard results for limit of recurrence relation?

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, ...
3
votes
1answer
84 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 ...
0
votes
0answers
17 views

Solving recurrence relation with $c=\Theta(\log(\log(n)))$

The master theorem in recurrence relations, i encounter with difficulty in solving problems, which have $c=\Theta $ $($of something$)$ or when it has $\log(n)$ or its variants instead of a simple ...
2
votes
1answer
66 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 ...
2
votes
2answers
93 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
61 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
20 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) = ...
6
votes
1answer
118 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
2answers
649 views

converting a recursive formula into a non-recursive formula.

We found a recursive formula for the following problem: For any positive integer $n$, let $b(n)$ be the number of ways that you can write $n$ as a sum using only the numbers 1, 2, and 3 where the ...
0
votes
3answers
43 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) ...
2
votes
2answers
92 views

How to solve the recurrence $T(n) = T(n-1) +\sqrt{n}$?

While solving the recurrence of the title I come to the series $$T(n) = \sqrt1 + \sqrt2 + \sqrt{3} + \cdots + \sqrt n.$$ Please somebody help me how to solve this.
0
votes
0answers
59 views

Partial Derivative of Integration

Suppose that I have some set of weight functions, $W = \{w_1(i,j), w_2(i,j),..., w_k(i,j)\}$, where each weight function is a Taylor polynomial in $\mathbb{R}^2$ with constants $c_{kn}$ where $n$ is ...
6
votes
2answers
85 views

Is the sequence $x_{n+1} = \frac{x_n + \alpha}{x_n + 1}$ convergent?

Fix $\alpha > 1$, and consider the sequence $(x_n)_n \geq 0$ defined by $x_0 > \sqrt \alpha$ and $$x_{n+1} = \frac{x_n + \alpha}{x_n + 1}, n = 0, 1, 2, \dots$$ Does this sequence converge, ...
0
votes
1answer
28 views

Solve the recurrence relation

Assuming that $n$ is a power of $2$, solve the recurrence relation $$T(n)=2T\left(\frac{n}{2}\right)+2$$ Take $T(2)=1$ and $T(1)=0$. Also how can this be done with the master theorem, if possible?
1
vote
1answer
277 views

Recurrence Relation, Discrete Math problem(Homework)

There is a disk, separated into n sections, as indicated in the graph. For each section, you can paint it with one color out of four: Red, Yellow, Blue, Green. The rule is adjacent sections can't have ...
5
votes
2answers
355 views

Series of sequence converges?

Given the recursively defined sequence $$ a_2 = 2(C+1)a_0 $$ and $$ a_{n+2}=\frac{\left(n(n+6)+4(C+1)\right)a_n - 8(n-2)a_{n-2}}{(n+1)(n+2)}. $$ that I got from the Frobenius method applied to an ODE, ...
1
vote
1answer
691 views

Legendre polynomials recurrence relation

How can i get? $$P_{n+1}=xP_n(x)-\frac{1-x^2}{n+1} P'_n(x)$$ $n>=0$ Also know as the leadder equation of the legendre polinomials i tried to use de recurrence relations as: ...
-4
votes
1answer
39 views

A recurrence involving nested cube roots [closed]

Solve the equatation $\sqrt[3]{x\sqrt[3]{x\sqrt[3]{x\sqrt[3]...}}} = 3$ Only have variant: 4 9 16 3
0
votes
2answers
26 views

Find the values of $r_1, r_2, r_3$ in the recurrence relation $a_n = r_1 a_{n-1} + r_2 a_{n-2} + r_3 a_{n-3} $

Consider the recurrence relation $a_n = > r_1 a_{n-1} + r_2 a_{n-2} + r_3 a_{n-3} $ for $n \ge 3$. The roots of the characteristic polynomial are $x = -1$ of multiplicity 2, $x= 3$ of ...
0
votes
1answer
32 views

How $L_n = L_{n-1} + n $ become $L_{n-2} + (n-1) +n $ and So on?

I am currently reading 'concrete mathematics' of knuth. I don't know how $L_n = L_{n-1} + n $ become $L_{n-2} + (n-1) +n $ and finally $L_0+1+2...+(n-2)+(n-1)+n $ can you please tell me?
6
votes
1answer
131 views

Recurrence Relation

How do I solve: $k(k+1)a_{k}=2(\lambda k-1)a_{k-1}+(a-\lambda^2)a_{k-2}$ where $\lambda$ and $a$ are constants, and similar other recurrence relations?
0
votes
3answers
131 views

How to show that closed form of Fibonacci number is roots ratio difference of $n^{th}$ power of roots to difference of roots of $x^2 - x - 1=0$

1.5 The Fibonacci numbers $1,1,2,3,5,...$ are defined by the recursion formula $x_{n+1} = x_n + x_{n-1}$, with $x_1 = x_2 = 1$. Prove that $(x_n, x_{n+1}) = 1$ and that $x_{n} = \frac{a^n ...
1
vote
2answers
60 views

Counting numbers with the digit 5: How to express recurrence relation in closed form?

I figured out the algorithm for finding the count of numbers containing the digit 5 for any power of 10. What is the correct way to express y in this formula? $f(x) = 9y + (x/10)$ Where y is ...
1
vote
1answer
223 views

Combinatorics - Catalan numbers recursive function proof by induction help

I'm trying to prove that $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1\leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number). For $n=1$ this is true. Assume it is true for $n=k$: ...
0
votes
1answer
26 views

Recurrence relation task

Can someone explain me this: $T(n)=-T(n-1)+2\times T(n-2)+3 \times 2^n+n$ According to Wolfram Alpha the answer is: $$ T(n) = c_1(-2)^n + c_2 + \dfrac{1}{18}n(3n + 7) + 3 \times 2^n - ...
1
vote
2answers
29 views

Finding the inhomogeneous solution

$x_{n+2} = x_{n+1} + 20x_n + n^2 + 5^n \text{ with } x_0 = 0 \text{ and } x_1 = 0$ How would I find the inhomogeneous solution for this since the homogenous solution is 0 given initial conditions?