If $x_1 = 3$, $x_{n+1} = \dfrac{1}{4-x_n}$ for $n \geq 1$, prove the sequence is decreasing and bounded below by $0$, above by $4$.
Want to show: $0 < x_{n+1} < x_n < 4$
I decided to do the bounded part first.
Base Case, $n=1$
$0 < 3 < 4$ [works]
IH
Suppose $0 < x_k < 4$, for some $k\in\mathbb{N}$
IS
Show $0 < x_{k+1} < 4$
We know $x_{k+1} = \dfrac{1}{4-x_k}$
We also know that $0 < x_k < 4$, by IH.
So we have:
$$\dfrac{1}{4} < x_{k+1} < \infty$$
But this doesn't show the boundness. Where have I went wrong?
Extension of the problem
As a bonus we can also find the explicit solution of the recursion
$$x_{n+1} = \frac{1}{4-x_n}, \,\,x_1 = 3$$
Letting
$$x_n = \frac{p_n}{q_n}$$
and comparing numerators and denominators we get a system of two linear recursions
$$p_{n+1} = q_n\tag {1} $$ $$q_{n+1} = 4 q_n - p_n\tag {2}$$
We can eliminate the variable $q_n$ by shifting the index in $(1)$ one unit, and then using $(2)$ which leads to
$$p_{n+2} = q_{n+1} = 4 q_n - p_n$$
now replacing $q_n$ by $(1)$ we find finally a recursion in $p_n$ only:
$$p_{n+2} = 4 p_{n+1} - p_n\tag{3}$$
The initial values can be taken as
$$p_1 = 3, p_2 = 1$$
The original variable is then given by
$$x_n = \frac{p_n}{p_{n+1}}\tag{4}$$
(I believe the reader can take it from here, so I pause for a while before giving the solution.)
Solution
The recursion can be solved assuming that
$$p_n = \lambda^n$$
Inserting this into $(3)$ leads to the characteristic equation
$$\lambda^2 = 4 \lambda -1$$
Notice that we obtain this equation also if we seek solutions $p$ which are independent of $n$.
The solutions are
$$\lambda_{+}=2+\sqrt 3\simeq 3.732050807568877\tag{5a}$$ $$\lambda_{-}=2-\sqrt 3\simeq 0.2679491924311228\tag{5b}$$
The general solution is then
$$p_n = A \lambda_{+}^n + B \lambda_{-}^n$$
where $A$ and $B$ are arbitrary constants to be determined by the intial conditions.
In our case the compete solution is
$$p_n = \frac{1}{6} \left(\left(33+19 \sqrt{3}\right) \lambda _-^n+\left(33-19 \sqrt{3}\right) \lambda _+^n\right)\tag {6}$$
The first $10$ values are
$$p_{1..10} = (3,1,1,3,11,41,153,571,2131,7953)$$
This sequence can be found in https://oeis.org/ under the ID $A001835 \;a(n) = 4*a(n-1) - a(n-2)$, with $a(0)=1, a(1)=1.$
The original variable $x$ is then, according to $(4)$ given by
$$x_n=\frac{\left(33+19 \sqrt{3}\right) \lambda _-^n+\left(33-19 \sqrt{3}\right) \lambda _+^n}{\left(33+19 \sqrt{3}\right) \lambda _-^{n+1}+\left(33-19 \sqrt{3}\right) \lambda _+^{n+1}}\tag {7}$$
It is interesting to extend the sequence to negative values of $n$. Between $-5$ and $+10$ we find
$$x_{(-5)..10}=\left\{\frac{7953}{2131},\frac{2131}{571},\frac{571}{153},\frac{153}{41},\frac{41}{11},\frac{11}{3},3,1,\frac{1}{3},\frac{3}{11},\frac{11}{41},\frac{41}{153},\frac{153}{571},\frac{571}{2131},\frac{2131}{7953},\frac{7953}{29681}\right\}$$
The graph is
We see that the limiting values for large positive and negative $n$ are the eigenvalues. This can also easily be derived from $(7)$.
Furthermore, all values are between $0$ and $4$. This proves the original assertion even if extended to all $n$.
Generalisation
The same method can be used to solve the more general recursion
$$x_{n+1} = \frac{a\; x_n + b}{c\; x_n + d}\tag {8}$$
where $a, b, c, d$ are constant coefficients.
An alternative method starts from the following procedure: calculate $x_{n+2}$ in terms of $x_n$, recognize the same form of the recursion with new coefficients, and find the rule by which the new coefficients are formed.
EDIT 15.04.17: Here is a reference in which this method is discussed extensiveley under the heading of "linear fractionl transformations": http://www.mathpages.com/home/kmath464/kmath464.htm