Hmmmm

In class we started learning about proofs. I saw a cool problem yesterday. I thought I'd try to prove it using the stuff we learned in class.

Prove that f(n) = 1 − n is the only integer-valued function that defined on the integers that satisfies the following conditions:
a) f(f(n)) = n for all integers n
b) f(f(n + 2) + 2) = n for all integers n
c) f(0) = 1

I'm going to try to write it symbolically. Let F be the set of integer valued functions defined on the integers. ∀ f ∈ F, ∀ n ∈ Z, (f(f(n)) = n ∧ f(f(n + 2) + 2) = n ∧ f(0) = 1) ⇒ f(n) = 1 - n

Proof. The indents work in my word processor, but I don't know why my indents didn't work here, so I used dashes.

First I want to prove that f is one to one. I'm going to try to write that symbollically. ∀ x, y ∈ Z, (f(f(n)) = n ∧ f(f(n + 2) + 2) = n ∧ f(0) = 1) ⇒ (f(x) = f(y) ⇒ x = y)

Assume x, y ∈ Z # x, y are generic
- Assume f(f(n)) = n, f(f(n + 2) + 2) = n, f(0) = 1 # assume first antecedent
- - Assume f(x) = f(y) # assume second antecedent
- - - Let z = f(x) = f(y)
- - - z ∈ Z # f is an integer valued function function
- - - f(f(x)) = f(z) = x # f is defined on the integers
- - - f(f(y)) = f(z) = y
- - - Then x = y
- - Then f(x) = f(y) ⇒ x = y
- Then (f(f(n)) = n ∧ f(f(n + 2) + 2) = n ∧ f(0) = 1) ⇒ (f(x) = f(y) ⇒ x = y)
Then ∀ x, y ∈ Z, (f(f(n)) = n ∧ f(f(n + 2) + 2) = n ∧ f(0) = 1) ⇒ (f(x) = f(y) ⇒ x = y)

Now f is one to one.

Assume f ∈ F, n ∈ Z # f, n are generic
- Assume f(f(n)) = n, f(f(n + 2) + 2) = n, f(0) = 1 # assume the antecedent
- - Assume n | 2 (n is even)
- - - Then ∃ x ∈ Z, n = 2x # definition of even
- - - f(f(2x + 2) + 2) = 2x = f(f(2x))
- - - f(2x + 2) + 2 = f(2x) # f is one to one
- - - f(2(x + 1)) = f(2x) - 2
- - - Let a_x = f(2x)
- - - a_(x + 1) = a_x - 2
- - - a_x forms an arithmetic sequence
- - - a_0 = f(2 * 0) = 1
- - - d = -2
- - - a_x = a_0 + dx = 1 - 2x
- - - f(2x) = 1 - 2x
- - - Then f(n) = 1 - n
- - Then n | 2 ⇒ f(n) = 1 - n
- - Assume ¬(n | 2) (n is odd)
- - - Then ∃ x ∈ Z, n = 2x + 1 # definition of odd
- - - f(f((2x + 1) + 2) + 2) = 2x + 1 = f(f(2x + 1))
- - - f(2(x + 1) + 1) + 2 = f(2x + 1) # f is one to one
- - - Let a_x = f(2x + 1)
- - - a_(x + 1) = a(x) - 2
- - - a_x forms an arithmetic sequence
- - - a_0 = f(2 * 0 + 1) = f(1) = f(f(0)) = 0 # f is one to one
- - - d = -2
- - - a_x = a_0 + dx = -2x
- - - f(2x + 1) = -2x
- - - Then f(n) = 1 - n
- - Then ¬(n | 2) ⇒ f(n) = 1 - n
- - Then (n | 2) ∨ ¬(n | 2) ⇒ f(n) = 1 - n
- - Then f(n) = 1 - n
- Then (f(f(n)) = n ∧ f(f(n + 2) + 2) = n ∧ f(0) = 1) ⇒ f(n) = 1 - n
Then ∀ f ∈ F, ∀ n ∈ Z, (f(f(n)) = n ∧ f(f(n + 2) + 2) = n ∧ f(0) = 1) ⇒ f(n) = 1 - n