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.

  1. Is this proof logically sound and are there any other 'better' methods?
  2. As a side question, if I didn't actually know that there was a solution, how would I prove the existence of a solution?
  • $\begingroup$ Just prove directly by induction that $f(n) = r^n f(0)$. The base case is $n=0$, and the inductive step is: $f(n) = r f(n-1) = r (r^{n-1} f(0)) = r^n f(0)$. $\endgroup$ – mjqxxxx Mar 27 '15 at 3:42
  • $\begingroup$ @mjqxxxx Induction lets me prove $g(n)$ is a solution. It doesn't let me prove that it is the only solution. $\endgroup$ – Scorpion_God Mar 27 '15 at 3:44
  • 1
    $\begingroup$ Yes, it does. You're proving that once $g(0)$ is specified, all values of $g(n)$ for $n>0$ are determined by the formula $g(n)=g(0)r^n$, so $g(n)$ must have the form $a r^n$ where $a$ turns out to be $g(0)$. $\endgroup$ – Tad Mar 27 '15 at 4:02
  • $\begingroup$ @Tad Cauchy's functional equation has a solution $f(x) = cx$ and this can be proved by induction for $x$ an integer. The solution can be proved for $x \in \Bbb{R}$ as well, but it is not the only solution (although I don't understand the proof). So why must induction give the only form of a solution in my case, but not with $f(x+y) = f(x) + f(y)$? $\endgroup$ – Scorpion_God Mar 27 '15 at 4:19
  • $\begingroup$ Because you're solving a linear recurrence, you're only trying to find values on a well-ordered set (the natural numbers) and they're all determined by the first few values (the first value, in your case), so induction applies nicely. The problem with $f(x+y)=f(x)+f(y)$ isn't the equation itself, but that you're asking for values on all real numbers. Indeed the equation $f(x)=r f(x-1)$ also admits an uncountably infinite vector space of solutions if you allow real values for $x$, since you can choose $f$ arbitrarily on $[0,1)$. $\endgroup$ – Tad Mar 27 '15 at 4:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.