Suppose I have a functional equation $f(n) = r \cdot f(n-1)$ where $r$ is a constant. This represents a geometric progression and a known solution is $g(n) = ar^n$ where $a = g(0)$. By intuition, $g(n)$ is the only solution. My proof of this is:
Let $g_1(n)$ and $g_2(n)$ be solutions. Then $h(n) = g_1(n) + g_2(n)$ is also a solution:
$$ \begin{align} h(n) &= g_1(n) + g_2(n) \\ &= r \cdot g_1(n-1) + r \cdot g_2(n-1) \\ &= r[g_1(n-1) + g_2(n-1)] \\ h(n) &= r \cdot h(n-1) \end{align} $$
Since $g_1(n) = c_1r^n$ and $g_2(n) = c_2r^n$ are known solutions, any solution $h(n)$ must satisfy:
$$ \begin{align} h(n) &= c_1r^n + c_2r^n \\ &= (c_1 + c_2)r^n \\ &= kr^n \end{align} $$
$h(n)$ is equivalent to $g(n)$, therefore $g(n)$ is the only solution.
- Is this proof logically sound and are there any other 'better' methods?
- As a side question, if I didn't actually know that there was a solution, how would I prove the existence of a solution?