Sequences, Induction and Recursion

Kayhan Erciyeş writes in the 6th Chapter of his book, "Discrete Mathematics and Graph Theory", the following about Sequences, Induction and Recursion:

I collected the answers to the most substantial questions regarding this chapter:

Define an arithmetic sequence.

An arithmetic sequence is a sequence of numbers in which each term after the first is obtained by adding a constant difference, called the common difference, to the preceding term. The nth term of an arithmetic sequence can be expressed as an​=a1​+(n−1)d, where a1​ is the first term, and d is the common difference.

What is the difference between an arithmetic sequence and an arithmetic series?

An arithmetic sequence is a list of numbers with a specific, constant difference between consecutive terms. An arithmetic series, on the other hand, is the sum of the terms of an arithmetic sequence. Essentially, the sequence lists the terms, while the series adds them up.

Define a geometric sequence.

A geometric sequence is a sequence of numbers where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the common ratio. The nth term of a geometric sequence can be expressed as an​=a1​×r(n−1), where a1​ is the first term, and r is the common ratio.

What is the summation formula for an arithmetic sequence with the first term a1​ and the last term an​?

The summation formula for an arithmetic sequence is given by Sn​=(n/2)*​(a1​+an​), where Sn​ is the sum of the first n terms, a1​ is the first term, and an​ is the nth (or last) term.

Proof:

Arithmetic Sequence Definition: The nth term of an arithmetic sequence can be written as: an​=a1​+(n−1)d where d is the common difference between consecutive terms.

Sum of the Sequence: The sum Sn​ of the first n terms is: Sn​=a1​+(a1​+d)+(a1​+2d)+⋯+[a1​+(n−1)d]

Writing Sn​ in Reverse Order: If we write Sn​ starting from the last term, we get:

Sn​=[a1​+(n−1)d]+[a1​+(n−2)d]+⋯+a1​

Adding the Two Expressions for Sn​: Adding each term in the sequence from the forward and reverse expressions side by side: 2Sn​=[2a1​+(n−1)d]+[2a1​+(n−1)d]+⋯+[2a1​+(n−1)d]

Notice that each term in the resulting sequence is essentially the first term plus the last term. Since there are n such terms, we can simplify the expression to:

2Sn​=n[2a1​+(n−1)d]

But we also know that an​=a1​+(n−1)d,

so we can write: 2Sn​=n(a1​+an​)

Solving for Sn​: Dividing both sides by 2 gives us the summation formula for an arithmetic sequence: Sn​=(n/2)​*(a1​+an​)

What is the summation formula for a geometric sequence with a common ratio r?

The summation formula for the first n terms of a geometric sequence is Sn​=a1​*(1-r^n​)/(1-r) for r≠1, where Sn​ is the sum, a1​ is the first term, r is the common ratio, and n is the number of terms.

Proof:

This subtraction cancels all terms except the first term of the original series, a1​, and the last term of the multiplied series, a1​r^n, leading to: Sn​(1−r)=a1​−a1​r^n = a1* (1-r^n)

Geometric Sequence Definition: The nth term of a geometric sequence can be expressed as an​=a1​⋅r(n−1).

Sum of the Sequence: The sum Sn​ of the first n terms is: Sn​=a1​+a1​r+a1​r2+⋯+a1​r(n−1)

Multiplying Sn​ by r: To manipulate the series, we multiply the entire sum by

rSn​=a1​r+a1​r2+a1​r3+⋯+a1​rn

Subtracting rSn​ from Sn​: Subtracting the two equations from each other: Sn​−rSn​=(a1​+a1​r+a1​r^2+⋯+a1​r^(n−1))−(a1​r+a1​r^2+a1​r^3+⋯+a1​r^n)

This subtraction cancels all terms except the first term of the original series, a1​, and the last term of the multiplied series, a1​r^n, leading to: Sn​(1−r)=a1​−a1​r^n = a1* (1-r^n)

Solving for Sn​: To isolate Sn​, divide both sides by (1−r) (since r≠1, 1−r is not zero and hence the division is valid): Sn=a1​*(1-r^n​)/(1-r)

What are the main steps of weak induction?

The main steps of weak induction are:

Base Case: Verify the statement is true for the initial value (usually n=0 or n=1).

Inductive Step: Assume the statement is true for some arbitrary positive integer k, and then show that the truth of the statement for k implies its truth for k+1.

What is the difference between weak induction and strong induction?

In weak induction, the inductive step assumes the statement is true for a single preceding instance (e.g., k) to prove it for the next instance (e.g., k+1). In strong induction, the assumption covers all preceding instances up to and including k to prove the statement for k+1. Strong induction is used when the proof for k+1 relies on multiple earlier cases, not just the immediately preceding one.

What is a recurrence relation?

A recurrence relation is an equation that recursively defines a sequence, where each term is a function of one or more preceding terms, with the starting terms specified. It expresses the nth term in terms of its predecessors.

What is a recursively defined function?

A recursively defined function is a function that is defined in terms of itself, using smaller inputs. It consists of one or more base cases that end the recursion and a rule that breaks down larger problems into smaller ones.

What are the properties of a recursively defined set?

A recursively defined set has a base case that specifies explicitly the simplest, undecomposable elements and a recursive step that defines how to build more complex elements from simpler ones.

Give an example of a recursive function.

An example is the factorial function, defined as n!=n×(n−1)! with the base case 0!=10!=1.

What is the base case of a recursive function and how is it defined?

The base case of a recursive function is the condition that stops the recursion by not calling the function again. It is defined to handle the simplest input directly, without further recursion, ensuring that the recursion terminates.

What is structural induction and how does it differ from the first and second principles of induction?

Structural induction is a method of mathematical proof used to prove statements about recursively defined structures (like trees or lists) by showing that the property holds for the base structure and that if it holds for an arbitrary structure, it also holds when the structure is expanded according to the recursive definition. Unlike the first (weak) and second (strong) principles of induction, which apply to statements about integers, structural induction applies to complex mathematical structures and proves properties by induction on the structure's size or shape.