Claim

The sum of the first [latex]n[/latex] positive integers is given by

[latex]1 + 2 + 3 + \cdots + n = \frac{n(n + 1)}{2}[/latex]

Proof:> Let’s try to understand the pattern by looking at a few small cases.

When [latex]n = 1: \quad 1 = \frac{1(1 + 1)}{2} = 1[/latex]

When [latex]n = 2: \quad 1 + 2 = 3 = \frac{2(2 + 1)}{2} = 3[/latex]

When [latex]n = 3: \quad 1 + 2 + 3 = 6 = \frac{3(3 + 1)}{2} = 6[/latex]

The formula seems to work. Imagine writing the numbers from [latex]1[/latex] to [latex]n[/latex] in a row

[latex]1 + 2 + 3 + \dots + (n - 2) + (n - 1) + n[/latex]

Now write them again in reverse order underneath.

[latex]n + (n - 1) + (n - 2) + \dots + 3 + 2 + 1[/latex]

If you add each column, you get

[latex](1 + n), (2 + n - 1), (3 + n - 2), ..., (n + 1)[/latex]

Each of these adds up to [latex]n + 1[/latex], and there are [latex]n[/latex] such pairs. So, the total of both rows is [latex]n(n + 1)[/latex]. But we only want the sum of one row, so divide by [latex]2[/latex] to obtain [latex]\frac{n(n + 1)}{2}[/latex].

[latex]\square[/latex]

Claim

The sum of the first [latex]n[/latex] positive integers is given by

[latex]1 + 2 + 3 + \cdots + n = \frac{n(n + 1)}{2}[/latex]

Proof

Let [latex]P(n)[/latex] be the proposition that:

[latex]1 + 2 + 3 + \cdots + n = \frac{n(n + 1)}{2}[/latex]

We will prove [latex]P(n)[/latex] is true for all integers [latex]n \geq 1[/latex] using induction.

Basis Step: Let [latex]n = 1[/latex]. Then [latex]1 = \frac{1(1 + 1)}{2} = 1[/latex], so the base case holds.

Inductive Step: Assume [latex]P(k)[/latex] is true for some arbitrary [latex]k \geq 1[/latex]. That is,

[latex]1 + 2 + 3 + \cdots + k = \frac{k(k + 1)}{2}[/latex]

We must show that [latex]P(k+1)[/latex] is also true, that is,

[latex]1 + 2 + 3 + \cdots + k + (k+1) = \frac{(k + 1)(k + 2)}{2}[/latex]

By the inductive hypothesis,

[latex]1 + 2 + 3 + \cdots + k + (k+1) = \frac{k(k + 1)}{2} + (k + 1) = \frac{(k + 1)(k + 2)}{2}[/latex]

So, the inductive hypothesis holds.

[latex]\square[/latex]

Claim

For all integers [latex]n \geq 1[/latex]

[latex]1 \cdot 1! + 2 \cdot 2! + 3 \cdot 3! + \dots + n \cdot n! = (n + 1)! - 1[/latex]

Proof

Basis Step: Let [latex]n = 1[/latex]. Then [latex]1 \cdot 1! = 1 = 2! - 1[/latex], so the base case holds.

Inductive Step: Assume true for [latex]n[/latex] and prove for [latex]n + 1[/latex]. By the inductive hypothesis,

[latex](1 \cdot 1! + 2 \cdot 2! + 3 \cdot 3! + \dots + n \cdot n!) + (n + 1)(n + 1)![/latex]

[latex]= (n + 1)! - 1 + (n + 1)(n + 1)![/latex]

[latex]= (n+1)![1 + (n+1)) - 1[/latex]

[latex]= (n + 2)! - 1[/latex]

The inductive hypothesis holds.

[latex]\square[/latex]

Claim: For all integers [latex]n \geq 1[/latex], the number formed by [latex]10^{n} - 1[/latex] is divisible by [latex]9[/latex].

Proof

Basis Step: Let [latex]n = 1[/latex]. Then [latex]10^{1} - 1 = 9[/latex], and [latex]9[/latex] is divisible by [latex]9[/latex].

Inductive Step: Assume that for some [latex]k \geq 1, 10^{k} - 1[/latex] is divisible by [latex]9[/latex]. That is,

[latex]10^{k} - 1 = 9m[/latex] for some integer [latex]m[/latex]

We must show that [latex]10^{k+1} - 1[/latex] is also divisible by [latex]9[/latex]. Consider

[latex]10^{k+1} - 1 = 10 \cdot 10^{k} - 1 = 10(10^{k} - 1) + 9[/latex]

By the inductive hypothesis, [latex]10^{k} - 1 = 9m[/latex], so

[latex]10^{k+1} - 1 = 10 \cdot 9m + 9 = 9(10m + 1)[/latex]

Hence, [latex]10^{k+1}[/latex] is divisible by [latex]9[/latex].

[latex]\square[/latex]

In the check digit system, we compute the sum of digits of a number, often using a loop.

SET digit_sum TO 0

FOR EACH digit IN number_string:

    CONVERT digit TO INTEGER

    ADD digit TO digit_sum

DISPLAY digit_sum

Here, we can define a loop invariant as:

“At the start of each iteration, digit_sum equals the sum of all digits processed so far.”

This invariant helps us reason about the loop's correctness. It ensures that the loop accumulates the correct total, and that, when the loop finishes, digit_sum holds the sum of all digits in the number.

Claim

The loop correctly computes the sum of all digits in number_string.

Proof

Let number_string be the string of digits of length [latex]n[/latex], indexed from [latex]0[/latex] to [latex]n - 1[/latex]. Let the digits be d_0, d_1, … d_{n-1}.

Basis Step: No digits have been processed, so digit_sum = 0. This is correct because the sum of zero digits is 0.

Inductive Step: Assume that after processing the first [latex]k[/latex] digits, the invariant holds. That is,

    digit_sum = d_0 + d_1 + … + d_{k-1}

Now, in the [latex](k+1)[/latex]th iteration, the digit d_k is converted to an integer and then added to digit_sum;. So now

digit_sum = d_0 + d_1 + … + d_k.

The invariant holds for [latex]k + 1[/latex].

[latex]\square[/latex]

Claim

Any amount of 12 cents or more can be made using only 4-cent and 5-cent coins.

Proof

Basis Step: The amount of 12 cents is made up of three 4-cent coins.

The amount of 13 cents is made up of two 4-cent coins and one 5-cent coin.

The amount of 14 cents is made up of one 4-cent coin and two 5-cent coins.

The amount of 15 cents is made up of three 5-cent coins.

These base cases are chosen because they are the smallest amounts for which we can explicitly show combinations of 4-cent and 5-cent coins that work. These base cases ensure that the inductive step (which builds the solution for [latex]n+1[/latex] using a solution for [latex]n-3[/latex]) has a solid foundation, since [latex]n-3[/latex] must be at least 12 for the step to work.

Inductive Step: Assume true for all values up to [latex]n \geq 15[/latex] and show for [latex]n+1[/latex]. Then by the inductive assumption,

[latex]n+1 = (n - 3) + 4[/latex], and [latex]n - 3 \geq 12[/latex]

>The inductive step works by assuming that we can make change for some amount [latex]n \geq 15[/latex], and then showing that we can also make change for [latex]n + 1[/latex] by simply adding a 4-cent coin. Since [latex]n + 1 - 4 = n - 3[/latex], and we’ve already proven we can make change for all amounts down to 12, this step ensures we can build up to any larger amount using previously verified combinations.

[latex]\square[/latex]

Claim

For any integer [latex]m[/latex], the following identity holds:

[latex]\lfloor \frac{n}{2} \rfloor + \lceil \frac{n}{2} \rceil = n[/latex]

Proof

A proof by cases is needed here, since the integer [latex]n[/latex] can be even or odd.

Case 1: Let [latex]n = 2k[/latex] for some integer [latex]k[/latex]. Then

[latex]\lfloor \frac{n}{2} \rfloor + \lceil \frac{n}{2} \rceil = k + k = 2k = n[/latex]

Case 2: Let [latex]n = 2k + 1[/latex] for some integer [latex]k[/latex]. Then

[latex]\lfloor \frac{n}{2} \rfloor + \lceil \frac{n}{2} \rceil = k + (k + 1) = 2k + 1 = n[/latex]

The identity is proven for all integers [latex]n[/latex].

[latex]\square[/latex]

Claim

Every binary string of length [latex]n[/latex] has [latex]2^{n}[/latex] possible combinations.

Proof

Basis Step: Let [latex]n = 0[/latex]. A binary string of length [latex]0[/latex] is the empty string, and there is exactly one such string. Thus, the number of binary strings of length [latex]0[/latex] is [latex]1 = 2^{0}[/latex].

Inductive Step: Assume that for some [latex]k \geq 0[/latex], the number of binary strings of length [latex]k[/latex] is [latex]2^{k}[/latex]. That is, there are [latex]2^{k}[/latex] binary strings of length [latex]k[/latex].

We must show that the number of binary strings of length [latex]k + 1[/latex] is [latex]2^{k+1}[/latex].

Each binary string of length [latex]k + 1[/latex] can be formed by appending either a 0 or a 1 to a binary string of length [latex]k[/latex]. For each of the [latex]2^{k}[/latex] strings of length [latex]k[/latex], we can create one new string by appending 0 and one new string by appending 1.

So, the total number of strings of length [latex]k + 1[/latex] is [latex]2 \cdot 2^{k} = 2^{k+1}[/latex]. The inductive step holds.

[latex]\square[/latex]