Proofs of Universal Statements: Mathematical Induction · Base of Induction

Lesson 7

Nikolai Chukhin · Alexander S. Kulikov

Let us prove the required statement by induction on \(n\).

Base \(n=1,2,3,4\). \[\begin{align*}1&=1^{2}\\ 2&=-1^{2}-2^{2}-3^{2}+4^{2}\\ 3&=-1^{2}+2^{2}\\ 4&=-1^{2}-2^{2}+3^{2}\\\end{align*}\]

Step \(n \to n+4\). If there is a representation for \(n\) (with \(k\) terms), then there is also a representation for \(n+4\), because \[(k+1)^{2}-(k+2)^{2}-(k+3)^{2}+(k+4)^{2}=4\ .\]

As in the change problem, this inductive proof naturally transforms into recursive code.

def represent(n):
    base_cases = {1: '+', 2: '---+', 3: '-+', 4: '--+'}

    if n in base_cases:
        return base_cases[n]
    else:
        return represent(n - 4) + '+--+'


for n in range(1, 15):
    print(f'\n{n}=', end='')
    for i, sign in enumerate(represent(n)):
        print(f'{sign}{(i + 1) ** 2}', end='')

1=+1
2=-1-4-9+16
3=-1+4
4=-1-4+9
5=+1+4-9-16+25
6=-1-4-9+16+25-36-49+64
7=-1+4+9-16-25+36
8=-1-4+9+16-25-36+49
9=+1+4-9-16+25+36-49-64+81
10=-1-4-9+16+25-36-49+64+81-100-121+144
11=-1+4+9-16-25+36+49-64-81+100
12=-1-4+9+16-25-36+49+64-81-100+121
13=+1+4-9-16+25+36-49-64+81+100-121-144+169
14=-1-4-9+16+25-36-49+64+81-100-121+144+169-196-225+256

For the curious 🤓

Again, recursion can be eliminated here. The code will be more compact, but it will be more difficult to reconstruct the original inductive proof from it.

def represent(n):
    return ('+', '---+', '-+', '--+')[(n - 1) % 4] + '+--+' * ((n - 1) // 4)