maths.free › Combinatorics & Graph Theory › Recurrences and generating functions
Recurrences and generating functions
Solving recurrence relations, and encoding a sequence as a power series.
A recurrence defines aₙ from earlier terms; a generating function Σ aₙ xⁿ packs the whole sequence into one function whose algebra does the counting. Picture it: the Fibonacci numbers growing by the golden ratio each step. Think it: linear recurrences with constant coefficients are solved exactly like constant-coefficient differential equations, a characteristic polynomial.
작업 예제 · fib(25)
단계별로
- F_0 = 0,; F_1 = 1
Each Fibonacci number is the sum of the two before it.
- F_{2} = F_{1} + F_{0} = 1
- F_{3} = F_{2} + F_{1} = 2
- F_{4} = F_{3} + F_{2} = 3
- F_{5} = F_{4} + F_{3} = 5
- F_{6} = F_{5} + F_{4} = 8
- F_{7} = F_{6} + F_{5} = 13
- F_{8} = F_{7} + F_{6} = 21
- \vdots
- F_{24} = F_{23} + F_{22} = 46368
- F_{25} = F_{24} + F_{23} = 75025
답을 드러내세요
이제 너 문제를 선택하거나, 타이핑하거나, 자신만의 문제를 그려보세요. 모든 단계는 그림으로 표시되며, 답은 질문을 할 때까지 숨겨져 있습니다.
여기서 사용된 기호
기호를 탭하면 전체 정의, 이미지 및 각 문자의 의미를 확인할 수 있습니다.
어떻게: Recurrences and generating functions
- Each Fibonacci number is the sum of the two before it.
사람들이 묻는 질문
Permutation or combination?
Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).
What is a graph in this sense?
Dots (vertices) joined by lines (edges), not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.
에 더 Combinatorics & Graph Theory
The counting principlesPigeonhole principle and inclusion, exclusionBinomial coefficients and Pascal's triangleGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs