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

learn more… | top users | synonyms (2)

0
votes
0answers
15 views

Solving a $2$ variable recurrence

I have a recurrence relation defined as : $A(i, j) = A(i, j-1) + A(i+1, j)$ where both $i$ and $j$ are less than a fixed variable $N$. Also, $A(i,1) = 1\:\:$ for all $1 \leq i \leq N$. $A(N, j) ...
0
votes
0answers
21 views

Prove equivalence between two Bessel functions relations

Given the following equation $$\frac{J_{n - 1} (u)}{uJ_n (u)} - \frac{K_{n-1}(w)}{wK_n(w)} = 0$$ (where $J$ is the Bessel function of the first kind, $K$ is the modified Bessel function of the ...
1
vote
0answers
16 views

In a recurrence relation, how do we know which order to terminate?

By employing Frobinious or Power Series approach, we my come up with a recurrence relation that is only solvable if we set any constant lower than $a_0$ or higher than $a_n$ vanish. For example, in ...
0
votes
0answers
18 views

Solve the Recurrence Relation to Get a Theta Bound

If I have $T(n)=T(n-5)+n$, how would I go about using induction to find a $\Theta$ bound for this. I was able to use a tree method to get that the bounds should be about $\frac{n^2}{5}$, but I am ...
0
votes
0answers
8 views

Practical example of non-homogenous recurrence relation

Could anyone provide a practical example of a non-homogenous recurrence relation from daily life? Sorry for asking such a trivial question.
5
votes
7answers
132 views

Convergence of the recursive sequence $a_{n+1}=\sqrt{2-a_n}$

I'm attempting to prove the convergence (or divergence, though I strongly suspect it converges) of a sequence defined as $a_{n+1}=\sqrt{2-a_n}$ with $a_1=\sqrt{2}$. I cannot use the monotonic ...
2
votes
2answers
46 views

Solving the recurrence $A_n = \sum_{k=1}^{n} 2^{k+1} A_{n-k}$

Let me ask a very simple question: Let $(A_n)$ be a sequence of integers defined by $A_0 = 1$ and $$\forall n \geq 1 : A_n = \sum_{k=1}^{n} 2^{k+1} \cdot A_{n-k}.$$ There is an explicit formula for ...
1
vote
2answers
36 views

Solve a linear system of equation involving some recursion

$$ \begin{align*} x_{1} &= 1 + x_{2}\\ x_{2} &= 1 + \frac{1}{2} x_{3} + \frac{1}{2} x_{1}\\ &\vdots\\ x_{i} &= 1 + \frac{1}{2} x_{i+1} + \frac{1}{2} x_{1}\\ &\vdots\\ x_{n-2} ...
1
vote
0answers
27 views

Solve this recurrence relation via a first order partial differential equation?

Find a general formula for $a_{n,k}$ , for $n,k\geq1$. We have initial values $a_{1,1}=1$, and $a_{1,k}=0$ for $k>1$. The recurrence relation is: $a_{n+1,1}=-a_{n,1}$ , for $n\geq1$ and ...
3
votes
2answers
53 views

If $\lim_{n \rightarrow \infty} a_n=L$ then $\lim_{n \rightarrow \infty} f(a_n)=f(L)$?

If we have for example $a_n=1+\sqrt{a_{n-1}}$ and $\lim_{n \rightarrow \infty} a_n=L$ then can I say that $ L=1+\sqrt{L}$? If it's so, what's the proof?
0
votes
1answer
19 views

Recurrence solving

Suppose recurrence is $a_{n+2}=a_{n+1}+6a_{n}$ Tried to solve it with solving $Fnc(n)=An^5+Bn^4+Cn^3+Dn^2+En+F$ Which gives $A = (-33/4), B = (365/4), C = (-1385/4), D = (2155/4), E = (-551/2), F = ...
0
votes
0answers
20 views

Mistake in recurrence relation text book?

I'm sorry for posting this here, but I would like to confirm my doubt about the correctness of the systems of equation in the textbook example. I enclosed an image.
1
vote
1answer
16 views

How to solve this recurrence $t(n) = ( 2^n )( t(n/2) )^2$ with $t(1)=1$?

I have been wondering about how to solve this recurrence but I don't get to any feasible solution. How can I do it?
0
votes
0answers
13 views

Recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$,$\sum\limits_{i=1}^{k}c_i < 1$ is linear

Let $L: \mathbb N_0 \to \mathbb N_0$ satisfy the recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$ with $c_i \geq 0$ for $i=0,\ldots, k$ and $\sum\limits_{i=1}^{k}c_i < ...
0
votes
1answer
27 views

Non-homogenous recurrence relation. How to find the particular solution?

I have enclosed one image of two textbook pages. There is a system of equation (see frame) on page 2. I do not understand why both terms can be set equal to 0 (zero)to solve it. Thank you for the ...
3
votes
1answer
27 views

Rational Points on Fibonacci-like Sequence of Polynomials

Let $\{a_n\}$ be a sequence of polynomials in $\mathbb{Q}[x,y]$ with $a_0=0,a_1=1$, and $$a_n=xa_{n-1}+ya_{n-2}$$ The first few look like $$a_3:y+x^2$$ $$a_4:2xy+x^3=x(2y+x^2)$$ $$a_5:y^2+3x^2y+x^4$$ ...
0
votes
0answers
20 views

Master Theorem for common recurrence

I have the following recurrence: $$T(n) = T\bigg(\frac{n}{2}\bigg) + O(n)$$ And I am trying to find the time complexity using the master theorem. So I have: $a = 1, b = 2$ $f(n) = O(n) = c(n)$ ...
0
votes
1answer
26 views

Find the order of elimination in Josephus Problem

Josephus Problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game. People are standing in a circle waiting to be executed. Counting begins at the first ...
0
votes
0answers
14 views

Big-Oh, Big-Omega, Big-Theta determination

I am given a recurrence relation and told to solve it. Once we solve it we are supposed to determine whether it is in $O(f(n)), \Omega(f(n))$, or $\Theta(f(n))$. The relation is $t_n = 2nt_{n-1}$. ...
2
votes
5answers
71 views

Limit of the sequence defined by a recurrence

Given a recurrence formula for an arithmetic sequence, $$U_{n} = \frac{1}{2+U_{n-1}}$$ Show that$$\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2+ ...}}}} = (SomeGivenValue)$$ How can we solve questions ...
0
votes
1answer
17 views

Recurrence relations with multiplication

I have a recurrence relation and I am not quite sure if I am solving it correctly. The relation is this: $t_n = 2nt_{n-1}$ where $t_0 = 1$ Here is how I went about solving this: First step is to ...
1
vote
1answer
23 views

Recursive formula for word problem.

I'm having problems with this recursion problem: Ann wants to buy along several weeks one dressing item which can be of two kinds: small ones -- hats and scarfs, and big ones -- dresses, suits, gowns ...
-3
votes
0answers
27 views

Recurrence / recursion [closed]

How to solve: A function F(n) satisfies the recurrence F(n) ≤ 4F(bn/2c) + n for all n ∈ N. Give an upper bound for F(n).
0
votes
0answers
10 views

Solving a recurrence relation with 2 variables and 2 boundary conditions.

I am having some problem with solving a recurrence relation. Probably, the problem can be solved using a generating function, unfortunately I do not know how to deal with the boundaries of this ...
-1
votes
1answer
62 views

find number of strings

Find the number of strings consisting of only a and b which have P occurrence of aa Q ...
0
votes
2answers
46 views

Showing that the sequence $ x_n = \frac {1}{1 + x_{n-1}} $ is convergent

Sequence is recursively defined by $ x_0 = 1 $ I managed to show it is boundness by showing that $ 0 \lt x_n \lt 1 $ Now, when i try to show monotony of the sequence i got the problem because ...
1
vote
1answer
34 views

Recurrence relation with blocks

We have a path of size $N$ and $1\times1$ blocks of $4$ colors: yellow, red, blue and white. We need to fill the path with blocks but we cannot have $2$ blocks of the same color in a row (we can have ...
1
vote
1answer
33 views

Non linear recurrence relation?

for $ f: \mathbb N \rightarrow \mathbb N $, How do I solve $ f_n - f_{n+2} = f_{n+3} \times (f_{n+2} - f_{n+4})$ I tried the generating function but it only seems to work for linear relations. any ...
1
vote
3answers
36 views

How many such sequences exist?

Here is a sequence, $a_1, a_2, a_3, \ldots$ that satisfy the following property: $a_{n+2} = a_{n+1}+a_n$, where $a_m$ is a positive integer for any $m$, and it is known that $a_7 = 2015$. How many ...
-1
votes
0answers
36 views

I'm having trouble with solving this discrete logistic dynamics problem [closed]

Show that a solution to the discrete logistic dynamics $$x_{n+1} = 4x_n(1-x_n) $$ can have the form of $$x_n= A\sin^\nu b^n. $$ Determine the $A,\nu, b$.
0
votes
1answer
25 views

Math Modeling Mortgage Question - $100000 mortgage paid over 30 yrs (360 months). [closed]

Your parents are considering a 30-year, \$100,000 mortgage that charges 0.5% interest each month. Formulate a model in terms of a monthly payment $p$ that allows the mortgage (loan) to be paid ...
-2
votes
1answer
34 views

Evaluating the given sequence $y_n = y_n(x) ( 0 \leq x \leq 1 )$ [closed]

Sequence is defined : $$y_1 = \frac{x}{2} \text{ and } y_n = \frac{x}{2} - \frac{y_{n-1}^2}{2}$$ Find the limit as $\mathbf{n}$ goes to infinity My problem is that i don't know how to show it's ...
-2
votes
4answers
84 views

how do I prove this recurrence relation? [closed]

The given information is: $f(1)$=$\frac{1}{2} $ $f(2)=f(1)+$$2\over{(2\times 2)}$ $f(3)=f(2)+$$3\over (2\times2\times2)$ $f(4)=f(3)+$$4\over(2\times2\times2\times2)$ $...$ $ ...
1
vote
2answers
48 views

General solution of recurrence relation [closed]

I am supposed to solve for the general solution of $f(n+2)=2(f(n+2))^2 -f(n+2)f(n)-2012$. I tried the method of generating functions but I am stuck with the power $2$ on the RHS. any other methods or ...
0
votes
1answer
24 views

Can we solve this recurrence relation using recursion tree method

The recurrence relation is given as follows: $T(n) = 2T(\sqrt{n})+1$ $T(1) = 1$ I tried to solve it with recursion tree as follows: But to find the number of levels that may occur, I have to ...
0
votes
0answers
21 views

Solving two variable(dependent) recursion relation

I have the following recursion relation: $d(m,k)=d(m-1,k) + d(m-1,k-1) + ... + d(m-1,k-\min(k+1,m)+1); \hspace{2cm} m=1,2,3,...; k=0,1,2,...,\binom{m}{2}.$ with the following conditions $d(m,0) = ...
2
votes
0answers
13 views

Recurrence $x_{k+1} = \sum_{i=1}^m \theta_i x_{k+1-i} + r_{k+1}$ solution

Let $x_k$ be the solution of the recurrence equation $$x_{k+1} = \sum_{i=1}^m \theta_i x_{k+1-i} + r_{k+1}$$ where $(r_k)$ is a general sequence. I'm trying to find a explicit solution for $(x_k)$ ...
0
votes
2answers
29 views

Proving with series $a_{n+1} = 3n + 1 - a_n$. [closed]

With series $a_{n+1} = 3n +1 - a_n$, prove that for any any natural $n$, $a_{n+2} = a_n + 3$. Any hints, clues? I don't have any idea how to begin.
2
votes
0answers
60 views

Closed form of $ a_n = 1 - \frac{a_{n-1} a_{n-2}}{4} $

Given the sequence $a_1 = 1$ and $a_2 = 1 $ with: $ a_n = 1 - \frac{a_{n-1} a_{n-2}}{4} $ Does there exist a closed form computing $a_n$ ? At the moment I have a problem getting a grip on the ...
0
votes
1answer
38 views

How to solve the recurrence relation $T(n)=aT(n-1)+bn^c$ with $T(1)=1$

How to solve this recurrence relation? $ T(n)=aT(n-1)+bn^c \\T(1)=1,$ where a, b, c are constant. I want to solve it using generating function, but get stuck. Could anybody help me?
0
votes
0answers
14 views

Getting closed-form for $f(x) = \sum_{k=0}^n (f(x-c_1 k-c_2)+1)$

I have to get closed-form for the recursive function $f(x) = \sum_{k=0}^n (f(x-c_1 k-c_2)+1)$ Where $c_1,c_2 \in \mathbb{N}$ $f(x) = 0 \,\,$ for $\,\, 0 < x < c_2$ $f(x) = -1\,\,$ for ...
2
votes
0answers
21 views

Is $\sum \frac{n+1}{b_{n+1}}$ irrational, when $b_1=2$ and $b_{k+1}=2^kb_k(b_k-1)+1$, $k\geq 1$?

Let the sequences of positive integers $$a_n=n$$ when $n\geq 1$, and $$b_{n+1}=2^nb_n(b_n-1)+1$$ for $n\geq 1$ taking $b_1=2$. I've computed with previous sequences to assert that satisfy the ...
0
votes
0answers
31 views

Recurrence relation to find run time-complexity

int function(int n){ if (n<=1) return 1; else return (2*function(n/2)); } What is the recurrence relation $T(n)$ for running time, and why ? I believe is ...
0
votes
0answers
28 views

Growth of solutions of a second order recurrence equation with variable coefficients

Is it possible to determine whether the solutions of a second order difference equation with variable coefficients $$x_{n+2}+a_n x_{n+1}+b_n x_{n}=0$$ are growing with $n$ (for example exponentially) ...
1
vote
2answers
62 views

$f(6)=144$ and $f(n+3) = f(n+2)\{f(n+1)+f(n)\}$, Then $f(7) =$?

Given that $f(6)=144$ and $f(n+3) = f(n+2) \cdot\Big(f(n+1)+f(n)\Big)$ $[$For $n = 1,2,3,4]$ Then find the value of $f(7)$. The solution is not unique but all of them are positive integers. I can't ...
0
votes
1answer
24 views

how do I prove that for a recurrence relation of the form $a(2 n)=2^k a(n), a(n)=c n^{k}$ for some constant $c$?

if this is difficult, I am satisfied with an example for when $k=2$ in other words, how do I prove that for a recurrence relation of the form $a(2 n)=4 a(n), a(n)=c n^{2}$ for some constant c?
1
vote
1answer
28 views

Proving uniqueness of a steady state

I have a difference equation $$ p_t^{1-\alpha}=\alpha\sigma(y-p_t-\frac{(\sigma p_{t-1}^\alpha+b)p_t^{1-\alpha}}{\alpha\sigma}) $$ where $\alpha \in [0,1]$ and everything else is >0. I need to ...
1
vote
1answer
12 views

Inhomogeneous recurrence relation

I shall solve an inhomogeneous recurrence relation: $$x_n=2x_{n-1}+2^n,\quad x_0=2$$ My approach: The homogeneous part: $$x_n=2x_{n-1}\implies x_n-2x_{n-1}=0$$ With $x_n=x^n$ approach: ...
0
votes
0answers
14 views

Bounds on the heights of the minimal polynomials of the algebraic coefficients of linear recurrence relations

Given a linear recurrence relation $$ a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k} $$ with characteristic polynomial $$ ...
0
votes
0answers
29 views

Time complexity of $T(n) = 2^n + 2\sum_{i=1}^{n-2} T(i)$

$$ T(n) = 2^n + 2\sum_{i=1}^{n-2} T(i)$$ $$ T(0) = 1 , T(1) = 2 $$ This is my $T(n)$, and I need to find its time complexity. I know the answer is $T(n) = \theta (n2^n)$, but I have a problem with ...