fairfolio
Saved Projects

Determining Combinatorial Sums Using Roots of Unity

CSEF · 2013 Mathematics & Software

Liang Zhou · North (John Wesley) High School, Riverside, Riverside County

Overview

Objectives/Goals The objective is to determine an algorithmically efficient closed-sum formula for the combinatorial sum nC0 + nCc + nC(2c) + nC(3c) + ... Methods/Materials Following a compilation of relevant background research and lemmas regarding roots of unity and Euler's formula, several numerical examples were analyzed in order to prove the main formula. Subsequently, the mechanics of the proof were discussed through an explanation of a clever application of the Binomial Theorem and its relation to the lemmas. The main formula was then further generalized to produce a corollary and various extensions. Finally, a Java program was developed to explore the efficiency of the main formula and its potential applications. Results The cyclic nature of roots of unity working in tandem with the combinatorial coefficients of the Binomial Theorem proved an especially powerful tool in "filtering" terms - with the appropriate substitutions, desired terms remained while unwanted ones were subsequently cancelled out. Using complexity analysis, simple computation of the combinatorial sum was determined to be O(n^2/c) while the main formula was O(c*log(n)). Conclusions/Discussion The project successfully determined an efficient formula for computing specific combinatorial series. The increased efficiency is especially important in large computations in applications such as encryption in computer science.

Summary statement

This project seeks to use the Binomial Theorem and roots of unity to prove an efficient formula for calculating combinatorial sums.

Help received

n/a

Competition history

  • CSEF 2013 Mathematics & Software · Entry S1499

Resources

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

Source: California Science & Engineering Fair public projects

Save projects to your library

Sign in with Google to keep track of projects you find interesting, organized into folders. An account also raises your daily allowance for “Has this been done?”, and lets you create a key for the MCP server with a much higher limit than anonymous use. Browsing stays public.

Continue with Google