Suppose $f : \mathbb{N} \longrightarrow \mathbb{N}$ is a function that satisfies $f(1) = 1$ and
$f(n + 1) =\{\begin{array}{cc} f(n)+2&\mbox{if}\ n=f(f(n)-n+1),\\f(n)+1& \mbox{Otherwise}\end {array}$

$(a)$ Prove that $f(f(n)-n+1)$ is either $n$ or $n+1$.
$(b)$ Determine$f$.
### Part (a): Prove that \( f(f(n) - n + 1) \) is either \( n \) or \( n+1 \).

1. **Base Case:**
   - Given \( f(1) = 1 \).
   - For \( n = 1 \), \( f(f(1) - 1 + 1) = f(1) = 1 \), which is \( n \).

2. **Inductive Step:**
   - Assume \( f(f(k) - k + 1) \) is either \( k \) or \( k+1 \) for all \( k \leq n \).
   - We need to show \( f(f(n+1) - (n+1) + 1) \) is either \( n+1 \) or \( n+2 \).

3. **Case Analysis:**
   - If \( f(n+1) = f(n) + 2 \):
     - Then \( f(f(n+1) - (n+1) + 1) = f(f(n) + 2 - (n+1) + 1) = f(f(n) - n + 2) \).
     - By the inductive hypothesis, \( f(f(n) - n + 2) \) is either \( n \) or \( n+1 \).
   - If \( f(n+1) = f(n) + 1 \):
     - Then \( f(f(n+1) - (n+1) + 1) = f(f(n) + 1 - (n+1) + 1) = f(f(n) - n + 1) \).
     - By the inductive hypothesis, \( f(f(n) - n + 1) \) is either \( n \) or \( n+1 \).

Thus, \( f(f(n) - n + 1) \) is either \( n \) or \( n+1 \).

\(\blacksquare\)

### Part (b): Determine \( f \).

1. **Hypothesis:**
   - Let \( \phi = \frac{1 + \sqrt{5}}{2} \) (the golden ratio).
   - Assume \( f(n) = \lfloor \phi n \rfloor \).

2. **Base Case:**
   - For \( n = 1 \), \( f(1) = \lfloor \phi \cdot 1 \rfloor = \lfloor \phi \rfloor = 1 \), which matches the given \( f(1) = 1 \).

3. **Inductive Step:**
   - Assume \( f(k) = \lfloor \phi k \rfloor \) for all \( k \leq n \).
   - We need to show \( f(n+1) = \lfloor \phi (n+1) \rfloor \).

4. **Case Analysis:**
   - If \( f(f(n) - n + 1) = n \):
     - Then \( f(n+1) = f(n) + 2 \).
     - We need to show \( \lfloor \phi (n+1) \rfloor = \lfloor \phi n \rfloor + 2 \).
     - Since \( \phi \) is irrational, \( \lfloor \phi n \rfloor + 2 = \lfloor \phi n + 2 \rfloor \).
     - \( \phi (n+1) = \phi n + \phi \).
     - Since \( \phi + 1 = \phi^2 \), \( \phi n + \phi = \phi n + \phi^2 - 1 = \phi (n+1) - 1 \).
     - Thus, \( \lfloor \phi (n+1) \rfloor = \lfloor \phi n + \phi \rfloor = \lfloor \phi n \rfloor + 2 \).

   - If \( f(f(n) - n + 1) = n+1 \):
     - Then \( f(n+1) = f(n) + 1 \).
     - We need to show \( \lfloor \phi (n+1) \rfloor = \lfloor \phi n \rfloor + 1 \).
     - Since \( \phi \) is irrational, \( \lfloor \phi n \rfloor + 1 = \lfloor \phi n + 1 \rfloor \).
     - \( \phi (n+1) = \phi n + \phi \).
     - Since \( \phi + 1 = \phi^2 \), \( \phi n + \phi = \phi n + \phi^2 - 1 = \phi (n+1) - 1 \).
     - Thus, \( \lfloor \phi (n+1) \rfloor = \lfloor \phi n + \phi \rfloor = \lfloor \phi n \rfloor + 1 \).

Thus, by induction, \( f(n) = \lfloor \phi n \rfloor \) for all \( n \).

\(\blacksquare\)

The final answer is \( \boxed{ f(n) = \lfloor \phi n \rfloor } \).