recursive formulas I'm studying linear algebra. I don't know how to deal with recursive formulas, for example


*

*fibonacci

*when you should find a big determinant of size $n$  (I think Vandermonde uses a recursive formula is found there, or is it induction?) 

*how do you go from a recursive formula to an explicit one?


Bad question, but I do need some guidance here. 
 A: (From a bit of a computer science perspective)
A recursive formula has two parts: a terminal condition, and a recursive call.
For instance, let's say Fibonacci numbers. Let's say that $f(n)$ will calculate the $n$-th Fibonacci number. Our domain is the natural numbers.
The function is therefore piecewise:
$$
f(n) =
\begin{cases}
1, & \text{if }n\text{ = 1 or $n$ = 2} \\
f(n-1) + f(n-2), & \text{if }n\text{ > 2}
\end{cases}
$$
The terminal condition is when $n = 1$ or $n=2$. In either case, the function returns a hard value.
The recursive call is the other part. We are defining the function (for certain values) in terms of itself. If $n$ is large enough, this will cause more recursive calls. Eventually, one of the recursive calls will be at $n=1$ or $n = 2$, so it will return a hard value. And then the recursive call that made that recursive call has a hard value, and so on.
Here's an example with $n =5$:\begin{align}
f(5) = f(3) + f(4)\\
= f(2) + f(3) + f(2) + f(1)\\
= 1 + f(1) + f(2) + 1 + 1\\
= 1+1+1+1+1\\
=\boxed{5}\\
\end{align}
Also, you could have a recursive formula for the determinant of an $n \times n$ matrix. Think about what the terminal condition would be: for which values of $n$ do you know a simple way to compute the determinant? Undoubtedly for $n=1$ and $n=2$, but maybe even $n=3$? And then think about how to recursively define the determinant of a larger matrix based on the determinants of smaller matrices (hint: cofactor expansion).
However, a warning: A recursive formula for determinants is very inefficient, and will take extremely long times to compute (even by a computer) for larger values of $n$.
A: The Fibonacci function is as follows:
$ F_{n}=F_{n-1}+F_{n-2} $
$ F_{0}=1, F_{1}=1 $
Normally, this is considered an homogeneous second order recurrence. In order to get to a general solution, you need to write down the characteristic polynomial and get the roots (in this case, it's the golden ratio). You can find a good reference on the book by Ralph Grimaldi (chapter 7 if I'm not wrong).
Algorithmically, you just do the computations. It takes time, since you actually are computing a few numbers on repeated times (it's a typical example on topics like Dynamic Programming).
