maths.free › Discrete Math & Logic › Sums and induction

Sums and induction

Closed forms for sums, and how induction proves them.

Σ k = n(n+1)/2 is the formula Gauss found at school; Σ k² and Σ k³ have closed forms too. Induction proves them: check n = 1, then show that if the formula holds for n it holds for n + 1.

Contoh yang dikerjakan · sum of k for k = 1 to n

Calculus · Series-And-Sums

Sum k for k = 1 to n

\sum_{k=1}^{n} k

Langkah demi langkah

  1. \sum_{k=1}^{n} k

    Write the sum out.

  2. 1 + 2 + 3 + 4 + \cdots

    The first few terms.

  3. = \frac{n \left(n + 1\right)}{2}

    Closed form (a standard summation formula, provable by induction).

Tunjukkan jawapan
\frac{n \left(n + 1\right)}{2}

Sekarang kau Pilih masalah, atau taip atau lukis sendiri. Setiap langkah, gambar, jawapan tersembunyi sehingga anda tanya.

Jaga kerja awak sendiri.

Akaun percuma menambah nota pada setiap pengajaran, rekod apa yang anda selesaikan, masalah yang anda selesaikan di satu tempat, dan seorang guru yang anda boleh tanya tentang halaman ini. Matematik itu sendiri terbuka kepada semua orang, sama ada anda log masuk atau tidak.

Daftar Masuk Log masuk

Simbol yang digunakan di sini

Tekan simbol mana-mana untuk definisi penuh, gambar, dan apa makna setiap huruf dalamnya.

Bagaimana untuk: Sums and induction

  1. Write the sum out.
  2. The first few terms.
  3. Closed form (a standard summation formula, provable by induction).

Soalan yang orang tanya

What makes mathematics "discrete"?

It deals with separate, countable objects (integers, graphs, statements) rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.

How does a proof by induction work?

Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.

What order should I take these lessons in?

Logic and proof first, because every later lesson proves things. Then induction, sets, relations and functions, counting, recurrences, graphs, Boolean algebra and automata, and finally algorithms and complexity, which use nearly everything before them.

Is discrete mathematics the same as the maths of computer science?

Largely. Data structures are graphs and trees, correctness arguments are induction, running times are recurrences and sums, circuits are Boolean algebra, and what a computer can do efficiently is the subject of the last lessons. It is also ordinary mathematics in its own right.

Do I need calculus for this course?

No. School algebra is enough. A little familiarity with limits helps when comparing growth rates, and the lesson on asymptotic analysis explains the one limit fact it uses.

Lebih dalam Discrete Math & Logic

Truth tablesProof by inductionAlgorithms and growth of functionsPredicate logic and quantifiersDirect proof, contrapositive and contradictionStrong induction and the well-ordering principleRelations: equivalence relations and partial ordersFunctions and cardinalityCounting: rules, choices and bijectionsThe pigeonhole principleSolving linear recurrence relationsGraphs: degrees, paths and connectivityTrees and spanning treesEuler and Hamilton paths