<s>[INST] How to go about solving this recurrence relation? In my discrete math class we were given the problem of finding an explicit formula for this recurrence relation and proving its correctness via induction.
$$a_n=2a_{n-1}+a_{n-2}+1, a_1 = 1, a_2=1.$$
I feel confident that I could prove the correctness of the formula through induction but I have no idea what the formula is. What kind of strategy should I use for solving recurrence relations like this?
 [/INST] Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write your recurrence as:
$$
a_{n + 2} = 2 a_{n + 1} + a_n + 1
$$
Multiply by $z^n$, sum over $n \ge 0$ and recognize the resulting sums:
$$
\frac{A(z) - a_0 - a_1 z}{z^2} = 2 \frac{A(z) - a_0}{z} + A(z) + \frac{1}{1 - z}
$$
Solve for $A(z)$:
$$
A(z) 
  = \frac{3}{4} \cdot \frac{1}{1 - (1 + \sqrt{2}) z}
      + \frac{3}{4} \cdot \frac{1}{1 - (1 - \sqrt{2}) z}
      - \frac{1}{2} \cdot \frac{1}{1 - z}
$$
Everything in sight are geometric series:
$$
a_n
  = \frac{3}{4} \cdot (1 + \sqrt{2})^n
      + \frac{3}{4} \cdot (1 - \sqrt{2})^n
      - \frac{1}{2}
$$
Proof by induction is superfluous, the derivation is the proof.
</s>