2 ms·

Like too many discrete math texts, the Characteristic Root Technique for Repeated Roots section does not give a proof of the forumla.

by gowld 2y ago

ykonstant 2y ago
It is a consequence of the form of the characteristic equation: if the double root is r, then expanding out x^2 - 2r + r^2 and matching terms we see that a = 2r and b = -r^2; in other words, the recurrence is a(n) = 2r a(n-1) - r^2 a(n-2). Divide by r^n to get the equivalent c(n) = 2c(n-1) - c(n-2), where c(n) = a(n)/r^n But this is the constant difference recurrence: c(n) - c(n-1) = c(n-1) - c(n-2) So c(n) is an arithmetic progression c(n) = x*n + y for some x and y given by the initial conditions. Thus the original sequence is a(n) = c(n) r^n = (x*n + y) r^n.
YZF 2y ago
This reminded me of something else... I remember contrasting the discrete math course I took (circa 1990) to Knuth's AoCP and how Knuth used generating functions to find the closed form for recursive series (and IIRC didn't even cover any other methods). The course I took didn't touch on generating functions and most other textbooks I read didn't either. Interesting to see that this book does cover the topic. I guess "discrete math" can be a lot of different things.
scythmic_waves 2y ago
I think because a full proof covering existence and uniqueness will either be really long or require tools from outside the scope of the text. E.g. there's a somewhat concise proof using linear algebra which I'll partially reproduce below. (I like this proof because the equation is derived from first principles rather than starting with an ansatz.) --- Let x_n be a sequence defined by the recurrence relation: x_{n+1} = a * x_{n-1} + b * x_n Observe that if we define a sequence of two-element vectors of successive elements: [x_0] [x_1] [x_2] [x_1], [x_2], [x_3], ... then we can form the relation in terms of matrix/vector multiplication: [x_1] = [[0 1]] [x_0] [x_2] [[a b]] [x_1] Let's name the sequence of vectors as y_n and call the matrix M: y_1 = M * y_0 We can get the next term in the sequence with another multiplication: y_2 = M * y_1 = M * (M * y_0) = M^2 * y_0 By induction we have: y_n = M^n * y_0 M has characteristic polynomial: r^2 - br - a = 0 with roots: r_1 = (b - c)/2 r_2 = (b + c)/2 c = √(b^2 + 4a) Therefore we have by diagonalization: y_n = S * [[r_1^n 0 ]] * S^(-1) * y_0 [[0 r_2^n]] where S is the matrix of eigenvectors. From here, we can finish our existence and uniqueness proofs from the existence and uniqueness of the eigenvalues of M.

Like too many discrete math texts, the Characteristic Root Technique for Repeated Roots section does not give a proof of the forumla.

by gowld 2y ago

Like too many discrete math texts, the Characteristic Root Technique for Repeated Roots section does not give a proof of the forumla.

ykonstant 2y ago

It is a consequence of the form of the characteristic equation: if the double root is r, then expanding out x^2 - 2r + r^2 and matching terms we see that a = 2r and b = -r^2; in other words, the recurrence is a(n) = 2r a(n-1) - r^2 a(n-2). Divide by r^n to get the equivalent c(n) = 2c(n-1) - c(n-2), where c(n) = a(n)/r^n But this is the constant difference recurrence: c(n) - c(n-1) = c(n-1) - c(n-2) So c(n) is an arithmetic progression c(n) = x*n + y for some x and y given by the initial conditions. Thus the original sequence is a(n) = c(n) r^n = (x*n + y) r^n.

YZF 2y ago

This reminded me of something else... I remember contrasting the discrete math course I took (circa 1990) to Knuth's AoCP and how Knuth used generating functions to find the closed form for recursive series (and IIRC didn't even cover any other methods). The course I took didn't touch on generating functions and most other textbooks I read didn't either. Interesting to see that this book does cover the topic. I guess "discrete math" can be a lot of different things.

scythmic_waves 2y ago

I think because a full proof covering existence and uniqueness will either be really long or require tools from outside the scope of the text. E.g. there's a somewhat concise proof using linear algebra which I'll partially reproduce below. (I like this proof because the equation is derived from first principles rather than starting with an ansatz.) --- Let x_n be a sequence defined by the recurrence relation: x_{n+1} = a * x_{n-1} + b * x_n Observe that if we define a sequence of two-element vectors of successive elements: [x_0] [x_1] [x_2] [x_1], [x_2], [x_3], ... then we can form the relation in terms of matrix/vector multiplication: [x_1] = [[0 1]] [x_0] [x_2] [[a b]] [x_1] Let's name the sequence of vectors as y_n and call the matrix M: y_1 = M * y_0 We can get the next term in the sequence with another multiplication: y_2 = M * y_1 = M * (M * y_0) = M^2 * y_0 By induction we have: y_n = M^n * y_0 M has characteristic polynomial: r^2 - br - a = 0 with roots: r_1 = (b - c)/2 r_2 = (b + c)/2 c = √(b^2 + 4a) Therefore we have by diagonalization: y_n = S * [[r_1^n 0 ]] * S^(-1) * y_0 [[0 r_2^n]] where S is the matrix of eigenvectors. From here, we can finish our existence and uniqueness proofs from the existence and uniqueness of the eigenvalues of M.