Homework 1
Due on Sept 21 Wednesday

1. Induction on Integers

Prove that $\forall n \in \mathbb{N}$,

(1)
\[3+3^2+\cdots+3^n=\frac{3^{n+1}-3}{2} \]

Proof:


2. Structural Induction

A set $S$ is defined as follows:
(1) $2\in S$
(2) if $x,y\in S$, then $2(x+y)\in S$.
(3) if $x,y\in S$, then $xy \in S$.
Prove that if $x\in S$ and $x\not=2$, then $x$ is divisible by 4.

Proof:


3. $\lambda$-Calculus

Reduce the following $\lambda$-terms to their normal form:
(1) $(\lambda a b c . c b a)zz(\lambda x y . x)$.
(2) $(\lambda z . z)(\lambda z . z z)(\lambda z . z y)$.
(3) $(\lambda y. ((\lambda x. y(xx)) (\lambda x. y(xx)))) (\lambda x.x)$

Answer:


4. Operator Precedence and Associativity

What does 3 @@ 5 @@ 7 + 1 evaluate to under the following three definitions? Explain.
(1) 

multThenInc :: Int -> Int -> Int
multThenInc x y = x * y + 1

infixl 3 @@
(@@) = multThenInc

(2) 

multThenInc :: Int -> Int -> Int
multThenInc x y = x * y + 1

infixr 3 @@
(@@) = multThenInc

(3) 

multThenInc :: Int -> Int -> Int
multThenInc x y = x * y + 1

infixl 7 @@
(@@) = multThenInc

(4) 

multThenInc :: Int -> Int -> Int
multThenInc x y = x * y + 1

infixr 7 @@
(@@) = multThenInc

(5) 

multThenInc :: Int -> Int -> Int
multThenInc x y = x * y + 1

infix 5 @@
(@@) = multThenInc

Answer: