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

learn more… | top users | synonyms (2)

1
vote
4answers
38 views

Computing good bounds for $P(n) = n + nP(n-1)$

What is the technique of computing the following recurrence? $$P(n) = n + nP(n-1)$$ (We assume $P(1) = 1$.) It is obvious that the lower bound for $P(n)$ is $n!$, and the upper bound is $(n+1)!$, ...
4
votes
0answers
172 views

Has this difference equation :$x_{n+1}=Ax^2_{n}-Bx^2_{n-1}$ been studied before?

I posted this problem before in MO but only I would like to know if this difference equation :$$x_{n+1}=Ax^2_{n}-Bx^2_{n-1}$$ where $A(\theta)= \cos(\theta)$ and $B(\theta) =\sin(\theta)$ are ...
1
vote
2answers
37 views

Linear Recurrence Problem

$f(0)=3, f(1)=1, f(n)=4f({n-1})+21f({n-2})$ Thought linear recurrence problems usually have subsets of things, and this seems like a new type for me. Can anyone help me out with hints?
2
votes
2answers
35 views

Help with recurrence $T(n) = T(n/2) + n$

I just need help seeing where I went wrong in this solution. $$T(n) = T\left(\frac{n}{2}\right) + n,~~~ T(1) = 0$$ By master theorem, this is $\theta(n)$. However, when I try to solve it, it ...
0
votes
2answers
45 views

Please help to find the formula for a relation

I'm trying to find the formula for the following relation: $ x_1 + x_2 + x_3 + x_4 = n $ where: $ 0 \leq x_1 \leq 3$ $ 0 \leq x_2 \leq 3$ $ x_3 \geq 0 $ $ x_3 \geq 0 $ Let $a_n$ be the ...
0
votes
0answers
29 views

How to predict intuitively the recurrence relations of josephus problem?

i have studied the Josephus problem from the concrete mathematics book.I have understand all related calculations discussed on that book.However i have some difficulties regarding to recurrence ...
0
votes
2answers
60 views

Finding a recursive formula for a string of the letters $A,B,C$ such that $AB, BC$ does not appear in

Find a recursive formula for a string of the letters $A,B,C$ such that $AB, BC$ does not appear in. $a_n=\begin {cases}A\text{____}a_{n-1}\\ B\text{____}a_{n-1}\\ C\text{____}a_{n-1}\\ ...
1
vote
1answer
44 views

Maximum nodes in AVL tree with distinct positive integers

Assuming that all keys in an AVL tree are distinct positive integers. Suppose that the root node of an AVL tree T holds the key N. What can be estimated largest possible number of nodes in T ? We ...
1
vote
4answers
35 views

Proving recurrence by mathematical induction

$f(1)=1,$ $f(n)=2f(n-1)+3$ ($\forall n>1$) has the following closed form solution $f(n)=2^{(n+1)}-3$ I understand that I can simply show that the recurrence is equal to $2^{(n+1)}-3$,but not ...
4
votes
2answers
115 views

Solving $ a(n+1) = a(n) + \frac{1}{a(n)}$ with $a(1) = 1 $

$ a(n+1) = a(n) + \frac {1}{a(n)}, a(1) = 1 $ What is the function that generates all the values of $a(n)$? Upon first inspection, this function appears to lie somewhere between a fractional power ...
-1
votes
0answers
24 views

writing a recurrence relation into a matrix

I have the following equations which I want to turn into matrices for 'simplicity' $$x_{t+1} = x_t + \beta v_t \exp(-\gamma v_t) \\ v_{t+1} = v_t - \beta v_t \exp(-\gamma v_t)$$. So I thought ...
0
votes
1answer
22 views

How to solve find a formula of homogeneous recurrence relation?

I try to find the formula for the following recurrence relation: $a_n = 2a_{n-1} + a_{n-2} $ $ a_0 = 1 $ $ a_1 = 3 $ I solve it as follow: $ a_n - 2a_{n-1} - a_{n-2} = 0 $ $ t^2 - 2t - 1 = 0 $ ...
2
votes
1answer
22 views

Solving recurrence relation without initial condition

Any idea on how I can approach this recurrence relation? It is very different to other questions I have encountered where there is only one term of $T(n)$ on the RHS, and the initial condition isn't ...
2
votes
2answers
62 views

Find a recurrence relation for the number of ternary strings of length n that do not contain two consecutive 0s or two consecutive 1s.

Note: Problem from "Kenneth Rosen's DM and it's applications" and solution from "Students solution guide for use with ... applications" Let P(n) be the number of strings not containg two containing ...
3
votes
0answers
31 views

Is this recurrence relation solvable?

Consider the following recurrence relation: \begin{equation} \gamma C_{m,n}+n\alpha C_{n,m}+ \beta \{C_{n+1,m}+ n C_{n-1,m}\}=EC_{n,m} \end{equation} where $\gamma, \alpha$ and $\beta$ are ...
1
vote
1answer
54 views

Recursive definition of a Gevrey-class function

Given the following Gevrey-class function $\Phi:\mathbb{R} \rightarrow \mathbb{R}$ $$\Phi_{s,T}(t) = \begin{cases} \begin{align} 0 \quad & t \le 0 \\ 1 \quad & t \ge T \\ ...
0
votes
1answer
18 views

Difference Equations - Reduction of order

I am asked to change the order of the following to a first order:$$Y_{t+2}-3Y_{t+1}+4Y_t=2$$ The approach I took was to create another equation and got the following system. $$\begin{cases} ...
9
votes
3answers
233 views

Quadratic Equation Recurrence?

So I was playing around with the following: Let $f_0(x) = x^2 - bx + c$. If $f_n(x)$ has roots $p$ and $q$ with $p > q$, then let $f_{n+1}(x) = x^2 - px + q$. The recurrence relation is rather ...
1
vote
2answers
41 views

Find $\lim\limits_{n\to\infty}y_n$ if $y_1=\frac{x}{2},y_n=\frac{x}{2}+\frac{y^2_{n-1}}{2},0\le x \le 1,n=2,3,…$

Is it a good approach to use induction? If $0\le x \le 1$ then $0\le y_1 \le \frac{5}{8}$. Suppose that $$0\le y_n \le \frac{5}{8}$$ and prove $$0\le y_{n+1} \le \frac{5}{8}$$ If ...
1
vote
2answers
19 views

Problem in substitution

I have a very stupid question, it seems that I've forgotten most of my math and can't figure this out. Considering the following, ...
0
votes
0answers
18 views

What are the “classical ways” to study a vectorial sequence defined by a recurrence relation

Suppose that $F$ is a smooth (at least continuously differentiable) function defined from $\mathbb{R}^n$ to $\mathbb{R}^n$. The target is to study the recurrence sequence $X_{n+1}=F(X_n)$ when $X_0$ ...
5
votes
1answer
125 views

How can I show that the sequence $x_n^2$ is bounded?

Two real sequences $(x_n)$ and $(y_n)$ are defined by $$x_{n+1}=x_n-(x_ny_n+x_{n+1}y_{n+1}-2)(y_n+y_{n+1})$$ $$y_{n+1}=y_n-(x_ny_n+x_{n+1}y_{n+1}-2)(x_n+x_{n+1})$$ with initial conditions $x_0=1$ and ...
2
votes
2answers
42 views

Solve $p_{n+1} + \frac 16 p_n = \frac 1 2 (\frac 5 6 ) ^{n-1}$

I'm trying to solve: $$p_{n+1} + \frac 16 p_n = \frac 1 2 \left(\frac 5 6 \right) ^{n-1}$$ with initial condition: $p_1 = 1$. First, I search particular solution of the form $p_n^* = \lambda (\frac ...
1
vote
2answers
32 views

Prove that $\lim\limits_{n\to\infty}y_{n}=\frac{1}{x}$ if $ y_{n}=y_{n-1}(2-xy_{n-1}), y_{i}>0,(i\in \mathbb{N}),x>0$

I have been asked to prove that $\lim\limits_{n\to\infty}y_{n}=\frac{1}{x}$ if $ y_{n}=y_{n-1}(2-xy_{n-1}), y_{i}>0,(i\in \mathbb{N}),x>0.$ In particular, what I would like to know is if it is ...
3
votes
4answers
73 views

Prove $ \lim\limits_{x\to\infty}y_{n}=\sqrt{x}$ if $y_{n}=\frac{1}{2}\left(y_{n-1}+\frac{x}{y_{n-1}}\right),n\in \mathbb{N},x>0,y_{0}>0$

Can someone say how to solve this problem? In solution, it says that it stars with $$\frac{y_{n}-\sqrt{x}}{y_{n}+\sqrt{x}}=\left(\frac{y_{n-1}-\sqrt{x}}{y_{n-1}+\sqrt{x}}\right)^2,n\ge 1$$ How to get ...
0
votes
0answers
18 views

How to do fixed point iteration with matrices?

I am trying to follow solution to solve $$\min[\mathbf{z},\mathbf{q+Mz}]=0$$ by fixed point iteration. If $\mathbf{M=C+B}$ then a recursive algorithm with $k$ showing the iteration can be written as ...
0
votes
1answer
20 views

Recurrence Problem Division Simplification Question

Given this problem with solution: http://postimg.org/image/gouhieo35/ I have a really simple question that i still can't understand. When he divided by $4^n$ how did 8C = 2C, 16C = C, and he ...
0
votes
1answer
33 views

Solving recurrence similar to Catalan number recurrence

Today i was solving a dynamic programming problem that is matrix chain multiplication and i come up with a recurrence, i tried for n=4 but :(. How can I solve this recurrence? It is similar to the ...
0
votes
1answer
28 views

Can this recurrence relation be solved with generating functions?

I have this recurrence relation, $$a_{n+1}=\frac{n+2}{n}a_n$$ with $a_1=1$. I've already solved this using a substitution approach by letting $a_n=\dfrac{(n+1)!}{(n-1)!}b_n$. This means ...
1
vote
1answer
36 views

Recursive random draw

Let $R(n)$ be a random draw of integers between $0$ and $n − 1$ (inclusive). I repeatedly apply $R$, starting at $10^{100}$. What’s the expected number of repeated applications until I get zero?
1
vote
1answer
67 views

the sequence $(1,t,t^2,t^3,…)$ is in a vector space [closed]

$A$ and $B$ are real constant numbers and V is the real vector space consisted of all infinite real sequences of the form $(c_0,c_1,c_2,c_3,...)$ which satisfy the recurrence relation $$c_{k+2} = ...
1
vote
0answers
41 views

Probability dice game, multiple turns

Alice and Bob are playing dices, Alice begins. If the current player gets a 6, he wins. If he gets 4 ou 5, he plays again. Else, the other player plays. Let $p_n$ (resp. $q_n$) be the ...
1
vote
1answer
37 views

Help with solving this Recurrence Relation

I really need help with this question Would anyone please give a simple step-by-step on how to solve this Recurrence Relation?? $a_n = 2a_{n-1} - 2a_{n-2}$ where $a_0 = 1$ and $a_1 = 3$ It would ...
3
votes
4answers
102 views

If $T(n)= T(n-1) + 2T(n-2)$

If $T(n)= T(n-1) + 2T(n-2)$ with $T(0)=0$ and $T(1) = 1$ What is $T(n)$ (in $Θ$–notation) in terms of $n$? I am trying to solve by substitution, but I am not sure if I am doing this right, as I ...
1
vote
1answer
24 views

Recurrence relation with characteristic equation that has only 1 root and complex roots

For the recurrence relation: $f_n = 2a_{n-1} - 2a_{n-2}$ I got the characteristic equation that had complex roots: $x^2 - 2x + 2 = 0$ that gave roots $i, -i$ and I wasn't sure how to continue the ...
2
votes
3answers
58 views

Examine the convergence of a sequence $\{a_{n}\}$ which is given by $a_{1}=a>0,a_{2}=b>0, a_{n+2}=\sqrt{a_{n+1}a_{n}},n\ge 1$

I used inequality between arithmetic and geometric means to show that a sequence $\{a_{n}\}$ is bounded: $$a_{n+2}=\sqrt{a_{n+1}a_{n}}\le \frac{a_{n+1}+a_{n}}{2}$$ Solving this, I get quadratic ...
-1
votes
2answers
42 views

How to solve recurrence equation with logarithms using the Master Theorem

how do you solve this equation of recurrence? $T(1) = 1$ $T(n) = 2T(\frac{n}{3})+n*log_2(n)+1$ The problem is the term $n*log_2(n)$. Can I only consider only $n$ as it's the larger then $log_(n)$ ...
-1
votes
0answers
29 views

analysis of the recursive relation

For what values of $\lambda$ will the following relation converge? (In other words, we want $\lim_{t\to \infty} u_t$ to exist.) $$u_{t+1} = u_t[1-\lambda e^{-u_t^2}].$$ The additional term $u_t^2$ ...
1
vote
0answers
17 views

Solving nonlinear first-order difference equation $ d_m = p_0 + p_1d_{m-1} + p_2(d_{m-1})^2 $ (extinction problem) [duplicate]

The steady-state equilibrium is $ d^* = \frac{1-p_1-\sqrt{(p_1-1)^2-4p_0p_2}}{2p_2} $. Based on a plot, I guessed the solution $ d_m = d^*(1-e^{-\alpha m}) $, which is pretty close but not correct. ...
2
votes
2answers
48 views

Sine Cosine Sequence?

Two real sequences $\{x\}$ and $\{y\}$ satisfy $$x_{n+2}=x_nx_{n+1}-y_ny_{n+1},$$ $$y_{n+2}=x_ny_{n+1}+y_nx_{n+1}.$$ Given $x_1=y_1=1/\sqrt 2$ and $x_2=y_2=1$, find closed forms of $x_n$ and $y_n$. ...
1
vote
4answers
53 views

Examine the convergence of a sequence ${a_{n}}$: $a_{n+1}=a_{n}-\sin(a_{n}),0\le a_{1}<\pi$

${a_{n}}$: $a_{n+1}=a_{n}-\sin(a_{n}),0\le a_{1}<\pi$ One way to do it is to show that the sequence is bounded and monotonous. How to show that it is bounded? If $$-1\le \sin(a_{n})\le 1$$ ...
5
votes
0answers
59 views

About the existence of a regular solution in a chaotic system

Show that for some choice of $x_1\in\mathbb{R}$, the sequence given by: $$ x_{n+1} = n-3^{x_n} $$ satisfies: $$ \lim_{n\to +\infty} x_n= +\infty. $$ I was able to prove the statement by showing ...
2
votes
4answers
86 views

Find $x_{n}$ if $x_{1}=a>0$ and $x_{n+1}=\frac{x_{1}+2x_{2}+…+nx_{n}}{n}$

Find $x_{n}$ if $x_{1}=a>0$ and $x_{n+1}=\frac{x_{1}+2x_{2}+...+nx_{n}}{n}$ I have a problem finding sum of $$x_{1}+2x_{2}+...+nx_{n}$$ I don't see the term $x_{2}$ because if $x_{1}=a$ for ...
-1
votes
1answer
22 views

How to compute the time complexity for a recurrence relationship?

I have to compute the time complexity for this recurrence relationship: T(n) = \begin{cases} c1, & \mbox{if } n\mbox{ = 1} \\ 8T(n/4) +n +c2, & \mbox{if } n\mbox{ > 1} \end{cases} Can ...
0
votes
0answers
50 views

Solving the recurrence $T(n) = 5T(n/7) +\log n$

I am trying to solve the recurrence $T(n) = 5T(n/7) +\log n$ to find the complexity of an algorithm. Although I solve this immediately with the Master Theorem if I try to solve the recursion I found ...
-1
votes
3answers
61 views

Find $n$th iterative term in recurrence relation $a_{n+2}-5a_{n+1}+6a_{n}=0$

The sequence $(a_{n})_{n\in \mathbb{N}}$ is given by recurrence relation : $$a_{1}=0,a_{2}=-6,$$ $$a_{n+2}-5a_{n+1}+6a_{n}=0\ \ (n\ge 1).$$ We get $$a_{3}=-30$$ $$a_{4}=-114$$ $$...$$ How to find ...
0
votes
2answers
32 views

Proving $T_n = 2\times 20^n + 4\times 8^n$ by mathematical induction

Given that $T_0 = 6$ and that $T_n$ satisfies the recurrence relation $$T_{n+1} = 20T_n - 8^n \times 48$$ I have the equation for any term $n$ to be; $T_n = 2\times 20^n+4⋅8^n$ I want to prove ...
2
votes
1answer
53 views

Solution of a recurrence equations

$T(1) = 1$ $T(n) = 2T(\frac{n}{3}) + n + 1$ How do you solve this equzione recurrence? I arrived at this point and then I don't know how to proceed... $2^kT(\frac{n}{3^k}) + ...
1
vote
0answers
22 views

Discrete time Pure-Birth process with population fraction

I would like to solve difference equations for a pure-birth process, where the rate of adding new nodes depends on the fraction of population. $$x_i(t+1)-x_i(t)=\alpha ...
-1
votes
1answer
19 views

Derivation of Properties of Associated Laguerre Polynomial

1.How to prove Rodrigues formula for Associated Laguerre Polynomial? 2.How to show they are orthonormal in the interval (0,infinity)? Also I want to find normalization constant? 3.How to prove ...