How to solve linear homogeneous recurrence relations?

Recurrence relations can be expressed in the closed-form using the characteristic equation. For example, in the "Recurrence Relation", we can express: g(n) = 3g(n - 1) - 2g(n - 2) This formula can be further expressed as so called "Closed Form"

g(n)=2**n (n power of 2, Python expression) Summary: Explicit Formula: g(n) = 3g(n - 1) - 2g(n - 2) Closed Form: g(n)=2**n Characteristic equation is induced based on the experience and guess. We found this method is effective when dealing with linear homogeneous recurrence relations. The method is such that: when we find f(n), we allocate x**n Each specific character is solved based on the factorization. Let's see the example solving the recurrence relation: g(n) = 3g(n - 1) - 2g(n - 2), Base cases: g(0) = 1, g(1) = 2 First, let's just take a glance. g(n) = 3g(n - 1) - 2g(n - 2) Then, determine(guess) as: x**n = 3x**(n - 1) - 2x**(n - 2) Do not worry about the meaning so much, since this is rather experimentally proved. Let's apply simplification by the algebra on x**n = 3x**(n - 1) - 2x**(n - 2),

Let's divide both side by x**(n - 2) Then, the equation become as: x**2 = 3x - 2 By applying the factorization, It expressed as (x - 1)(x - 2)=0 　 　<= This is so called "characteristic equation" Now, we need to understand a concept so called multiple roots, or repeated roots. In this case, both are 1 --- Note：Let's learn this concept later Thus; g(n) = s1**n + t2**n (general solution) The expression denoting the infinite set of solutions to a recurrence relation without initial values is called the general solution to the recurrence relation. By the definition, g(0) = s + t = 1, g(1) = s + 2t = 2 By solving this simultaneous equations, t = 1, s = 0 Thus; g(n) = s1**n + t2**n = 2**n Therefore, g(n) = 2**n ----- END ================================================================= --- Note: multiple roots For example, assume we found a characteristic equation such that ((x - 2)**4)((x - 3)**2) = 0 (x-2)**4 has multiplicity 4 and root 2, such as 2**n, n2**n, n**2(2**n), n**3(2**n) Thus, this can be expressed as "addition" such that:

a1*2**n + a2*n2**n + a3*n**2(2**n) + a4*n**3(2**n) -- root 2 is induced by (x - 2) In the same way, ((x-3)**2) has multiplicity 2 and root 3, such as 3**n, n3**n This is expressed by addition such that:

a5*3**n + a6*n3**n -- root 3 is induced by (x-3) Thus, g(n) = a1*2**n + a2*n2**n + a3*n**2(2**n) + a4*n**3(2**n) + a5*3**n + a6*n3**n In order to produce the closed-form, in this case, we need 6 bases: Base cases: g(0), g(1), g(2), g(3), g(4), g(5) By the 6 simultaneous equations, we induce a1, a2, a3, a4,5 In this way, Fibonacci number can be solved by using characteristic equation.

https://en.wikipedia.org/wiki/Fibonacci_number

Keynote: It is hard for human to find a specific formulas result by just knowing the explicit formula. We need closed-from to mathematically derive the answer. However, computer can deliver the answer just by programming the explicit formula to plug in.