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.

Megdolgozott példa · fib(25)

Number-Theory · Sequences

Fib(25)

25

Lépésről lépésre

  1. F_0 = 0,; F_1 = 1

    Each Fibonacci number is the sum of the two before it.

  2. F_{2} = F_{1} + F_{0} = 1

  3. F_{3} = F_{2} + F_{1} = 2

  4. F_{4} = F_{3} + F_{2} = 3

  5. F_{5} = F_{4} + F_{3} = 5

  6. F_{6} = F_{5} + F_{4} = 8

  7. F_{7} = F_{6} + F_{5} = 13

  8. F_{8} = F_{7} + F_{6} = 21

  9. \vdots

  10. F_{24} = F_{23} + F_{22} = 46368

  11. F_{25} = F_{24} + F_{23} = 75025

Mutasd meg a választ!
F_{25} = 75025

Most te. Válasszon egy problémát, vagy gépelje vagy rajzolja le a saját. Minden lépés, a kép, a válasz elrejtve, amíg nem kérdezi.

Dolgozz tovább!

Egy ingyenes fiók jegyzeteket ad minden leckéről, egy feljegyzést arról, hogy mit végeztél el, a megoldott problémáidról egy helyen, és egy oktatót, akit megkérdezhetsz erről az oldalról. A matematika maga mindenki számára nyitva áll, bejelentkezve vagy sem.

Regisztrálj! Bejelentkezés

Itt használt szimbólumok

Koppintson a teljes definícióra, a képre és arra, hogy mit jelent minden betű.

Hogyan kell: Recurrences and generating functions

  1. Each Fibonacci number is the sum of the two before it.

Kérdések, amiket az emberek feltesznek

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.

Még több 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