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

learn more… | top users | synonyms (2)

0
votes
1answer
41 views

Recurrence relation for a string over the letters $\{A,B,C,D\}$ such that each $A$ appears before $C$

Find a recurrence relation for the number of strings of length $n$ that's composed of the letters $\{A,B,C,D\}$ such that each $A$ appears before $C$. $a_n=\begin{cases} A\text{______} = a_{n-1} ...
6
votes
2answers
71 views

How to evaluate $\lim_{ n\to \infty }\frac{a_n}{2^{n-1}}$, if $a_0=0$ and $a_{n+1}=a_n+\sqrt{a_n^2+1}$?

Let $a_1,a_2,..,a_n$ be sequence of real numbers such that $a_{n+1}=a_{n}+\sqrt{1+a_n^2}$ and $a_0=0$. How to evaluate $\lim_{ n\to \infty }\frac{a_n}{2^{n-1}}$ ?
0
votes
2answers
61 views

Solving $g(n)=2g(n-1)+n+2^n$

I am learning how to solve recurrence relations and I have an equation that got me to a dead end: $$g(n)=2g(n-1)+n+2^n$$ My problem is the non-homogeneous part.
0
votes
0answers
26 views

Can recurrences involving $\gcd$ be solved?

Can recurrences of the form $$ \sum_{i=1}^n a_iX_i=\gcd(n, X_n) $$ Where $a_i$ are constant coeficients. $a_i,X_i$ are integers. $a_n\neq0$. For $n \geq 2$ be solved? Here is an example: $$ ...
1
vote
2answers
36 views

Find $r$, given that $F_r= 2F_{101}+F_{100}$

Find $r$, given that $F_r= 2F_{101}+F_{100}$. We know that the recurrence relation for the Fibonacci sequence is $F_n= F_{n-1}+F_{n-2}$ and that $F_0 = F_1 = 1$, but how to proceed further?
0
votes
2answers
42 views

Find coefficient of $X^{12}$

I need to find coefficient of $X^{12}$ in $({1-2X})^{19}$. What is the formula to solve it?I only know about $$\frac{1}{a-X}=\frac{1}{a}\sum_{r=0}^\infty \frac{X^r}{a^r}$$ ...
0
votes
1answer
19 views

Recurrence relation for ways to color a circle with two colors such that there can't be two adjacent reds

Find the recurrence relation for how many ways there are to color a carousel with a circumference of length $n$ with two colors, red and blue such that no two reds will be adjacent This is like ...
0
votes
0answers
28 views

this function is known ?: $h_{n+1}(x)=h_n(x)^2+h′_n(x)$

Let $f(x)=x^{1/x}$, so the first derivative of $f(x)$ is $f′(x)=f(x)∗(1−ln(x))/x^2$, and in general, $f^n(x)=f(x)∗h_n(x)$, where $f^n(x)$ is the nth derivative of $f(x)$. I was trying find this ...
1
vote
1answer
43 views

Solving the recurrence $T(n) = \sqrt n T(\sqrt{n}) + \sqrt{n}$

A former student of mine was TA-ing an algorithms class last quarter and asked students to solve this famous recurrence relation: $$T(n) = \sqrt n T(\sqrt{n}) + n$$ There are several ways to solve ...
0
votes
0answers
38 views

Solving a Recurrence for a Mathematical Game

The problem is: Two players take turns removing coins from a pile. There are initially $n$ coins, and on each turn, a player can remove $a_1, a_2, \dotsc, a_k$ coins. The player who cannot remove ...
0
votes
1answer
44 views

Can You Help Me With This Logistic Difference Equation?

In population biology, the following equation is the Pielou Logistic Equation, is used to model population with non-overlapping generations $$x_{n+1} = \frac{\alpha x_{n}}{1+\beta x_{n}}$$ Show ...
2
votes
1answer
40 views

FSR function of the component-wise product, sum, of two LFSR sequences

Let $T_1$, $T_2$ be two $m$-sequences over $\mathbb{F}_q$ of length $q^n-1$, say $T_1 = (\text{Tr}_{q^n | q}(\alpha^i))_{i \geq 0}$, $T_2 = (\text{Tr}_{q^n | q}(\beta^i))_{i \geq 0}$, for some ...
0
votes
1answer
31 views

Find the asymptotic tight bound for $T(n)=T(n-1)+n lg n + n$ and for $T(n)=n^2 \sqrt{n}T(\sqrt{n})+n^5lg^3n+lg^5n$

I am stucked at this problem: Find the asymtotic tight bound for the following recurrences: (Assume that $T(n)$ is constant for sufficiently small $n$) (1) $T(n)=T(n-1)+n lg n + n$ (2) $T(n)=n^2 ...
1
vote
4answers
40 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
177 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
38 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
37 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
46 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
43 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
67 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
51 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
42 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
138 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 ...
0
votes
1answer
28 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
34 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
84 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
33 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
61 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
23 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
252 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
43 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
21 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
19 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
140 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
44 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
74 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
19 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
38 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 ...
3
votes
4answers
61 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
67 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
0answers
47 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
2answers
45 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
115 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
29 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 ...
3
votes
3answers
62 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
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
50 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$. ...