Here's another example of a recurrence relation that is not well defined. $$ d(n) = \frac{1}{n-3} d(n-1), \ \ d(0) = 1 $$ The problem here is at $n=3$, since in that case we have a divide-by-zero error.
Finally, here's an interesting example. Consider the function $c$ defined as $$ c(n) = \left\{ \begin{array}{cl} \frac{n}{2} & \text{ if even}(n)\\ \frac{3n+1}{2} & \text{ otherwise} \end{array} \right. $$ This is not a recurrence relation, by the way, just a plain old function definition. In any event, what's interesting is to start at a number, and continually apply this function until you get to 1. Like this:18,9,14,7,11,17,26,13,20,10,5,8,4,2,1Getting to 1 is a 13-element sequence! So we might ask for function $cc(n)$ that counts the length of the sequence starting at $n$. So $cc(18) = 13$. This we can define as $$ cc(n) = 1 + \left( \text{ if even}(n)\text{ then } cc\left(\frac{n}{2}\right)\ \text{else } cc\left(\frac{3n+1}{2}\right) \right),\ \ cc(1) = 1, cc(0) = 0 $$ The interesting thing is that nobody knows whether this sequence is well-defined or not! The problem of whether from any starting number the sequence always ends up at 1 (as opposed to going on forever) is a famous unsolved problem known as the Collatz Conjecture. Look it up! In any event, the point is that whether a function is well-defined can be tricky. If you look at the recursive expression for $cc(\cdot)$, you'll notice that, to use programming nomenclature, we have a recursive call that does not move us closer to the base case. This opens the door to problems. So we will stick to recurrences where each "recursive call" moves us closer to the base case.
$S_n = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$, and $P_n = 1 + r + r^2 + \cdots + r^n = \frac{r^{n+1}-1}{r-1}$.
You should just know those. Perhaps you could get them tatood somewhere where they would make a handy reference. In any event, those sums are really important - they come up all the time.Sums like these may seem like a different topic than recurrence relations, but they're not. Why? Because you can always rewrite the sum as a recurrence:
$S_n = \underbrace{1 + 2 + \cdots + (n-1)}_{S_{n-1}} + n$, so $S_n$ is defined by $S(n) = S(n-1) + n,\ \ S(0) = 0$.
$P_n = \underbrace{1 + r + r^2 + \cdots + r^{n-1}}_{P_{n-1}} + r^n$, so $P_n$ is defined by $P(n) = P(n-1) + r^n, \ \ P(0) = 0$.
So when we are studying recurrence relations, we are also studying sums!There is a special notation for sums that you will often encounter, "Σ notation". The idea is this: for function $f$ with domain $\mathbb{Z}$, the notation $\Sigma_{i=a}^b f(i)$ is defined as: $$ \Sigma_{i=a}^b f(i) = f(a) + f(a+1) + f(a+2) + \ldots f(b) $$ I.e. you add up the values of $f$ at all integer values in $\{a,a+1,a+2,\ldots,b\}$. So, for example, $1+2+\ldots+n = \Sigma_{i=1}^n i$. and $1+r+r^2+\ldots+r^n = \Sigma_{i=0}^n r^i$. One important detail is what to do about "empty sums", i.e. sums where the upper bound $b$ is actually less than the lower bound $a$? In this case, the value of the sum is "0", the additive identity. Note: We went over in class how this notation is closely related to programming contexts. In particular, the "scope" of variable $i$ is limited to the $\Sigma$ expression. It's just like a local variable in a function, or the counter variable in a "for" loop.
The same construct exists for products, except we use $\Pi$. So, for example, $1\cdot2\cdot3\cdot\ldots\cdot n = \Pi_{i=1}^n i$. The value of an empty product is the multiplicative identity, i.e. "1".
In fact, we can do this for any binary operator. For example, $\bigwedge_{i=1}^n x_i = x_1 \wedge x_2 \wedge \ldots \wedge x_n$.