1. reccurrence_equations.pdf

대학원 과정 이산수학 영문 레포트(리써치 베이스)입니다.

1 Introduction Recurrence equations

2 Second order linear recurrence equations

2.1 General solution - introduction
2.2 Generating Functions
2.2.1 Homogeneous equation
2.2.2 Non-homogeneous solutions
2.3.1 homogeneous solution
2.3.2 particular solution
2.3.3 Solution to the full problem
3 Conclusion

In this project, solutions to second order linear recurrence equations with constant coeffi- cients have been investigated. We have used generating functions to derive the general solution to the homogeneous equation and we show that in general the particular solution is complicated to find. By limiting the right hand side (RHS) in the equation to a polynomial-exponential family of functions we can however find the particular solution in a closed form.


We show that the homogeneous solution is a linear combination of exponential functions and the particular solution is of the same form as the RHS of the equation with an increase in polynomial order if any part of the RHS can be expressed in terms of the homogeneous solution, so called resonance.
Using generating functions to solve such problems require a lot of computations and par- tial fractions expansions. Therefore a more hands on approach is presented and discussed where the forms of the homogeneous and particular solutions are assumed, based on the pre- viously derived solutions.


The homogeneous solution is determined by solving a characteristic equation, and using the characteristic roots together with the assumed form of the solution the solution is given with two undetermined coefficients. The particular solution is found by substituting the assumed form of the particular solution into the equations and solving a linear system of equations. Finally the unknown coefficients are determined from the initial conditions.

영문이산수학, 이산수학레포트, 대학이산수학, 대학원이산수학, Discrete Mathematics, 영문이산수학레포트

[1] Tang M., Tang V.T. Using Generating Functions to Solve Linear Inhomogeneous Recurrence Equa- tions, Proceedings of the 6th WSEAS International Conference on Simulation, Modelling and Opti- mization, Lisbon, Portugal, September 22-24, 2006.

[2] Parag H. Dave; Himanshu B. Dave, Design and Analysis of Algorithms, p.709, Pearson Education India, 2007, ISBN 978-81-775-8595-7

[3] Kauers, M., Paule P., The Concrete Tetrahedron, Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates, p.66 Texts and Monographs in Symbolic Computation, 2011, ISBN: 978-3-7091-0445-3

[4] Epp, Susanna, Discrete Mathematics with Applications, 4th ed., p317-319, DePaul University, BROOKS/COLE CENGANGE Learning, 2011

[5] Cull P.; Flahive M.E, Robson, R.O., Difference equations: from rabbits to chaos, p.74, New York : Springer, c2005, ISBN:0387232338