TAILIEUCHUNG - Báo cáo toán học: "The Combinatorialization of Linear Recurrences"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: The Combinatorialization of Linear Recurrences. | The Combinatorialization of Linear Recurrences Arthur T. Benjamin Harvey Mudd College Claremont CA USA benj amin@ Halcyon Derks Duke University Durham NC USA hderks@ Jennifer J. Quinn University of Washington Tacoma Tacoma WA USA j j quinn@ Submitted Mar 24 2011 Accepted Jun 1 2011 Published Jun 11 2011 Mathematics Subject Classifications 05A19 11B37 Abstract We provide two combinatorial proofs that linear recurrences with constant coefficients have a closed form based on the roots of its characteristic equation. The proofs employ sign-reversing involutions on weighted tilings. 1 Introduction Given a recurrence relation and initial conditions the goal is frequently to find a closed form expression for an arbitrary term in the sequence. While this is not always possible the solution for homogeneous linear recurrences with constant coefficients is completely understood. So many of our favorite number sequences such as Fibonacci numbers and their generalizations are precisely these. Each has beautiful tiling interpretations that make proving many identities a matter of asking a combinatorial question and answering it two different ways or describing two sets of known cardinalities and finding a correspondence between them bijection many-to-one mapping almost one-to-one correspondence . For example the Fibonacci numbers are defined by a second order linear recurrence with coefficients of 1 and special initial conditions. More precisely F0 0 F1 1 and for n 2 Fn Fn_1 Fn-2. For n 1 Fn is frequently interpreted as the number of tilings of a 1 X n 1 -board using 1 X 1 squares and 1 X 2 dominoes 5 . Since any such tiling must end with a square or a domino it clearly satisfies the Fibonacci recurrence and a few quick checks verify the initial conditions for n 2 and n 3 and we happily THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2 2011 P12 1 declare F0 0 and F1 1 . Binet s formula reveals the closed form solution for the Fibonacci numbers to be F n 1 1

Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.