Search code examples
leanproof-assistant

erase common constant of equation using leanprover


I want to prove below goal.

n_n: ℕ
n_ih: n_n * (n_n + 1) / 2 = arith_sum n_n
⊢ (n_n + 1) * (n_n + 1 + 1) / 2 = n_n + 1 + n_n * (n_n + 1) / 2 

ring, simp, linarith is not working. Also I tried calc, but it too long. Is there any automatic command to erase common constant in equation?


Solution

  • I would say that you were asking the wrong question. Your hypothesis and goal contain / but this is not mathematical division, this is a pathological function which computer scientists use, which takes as input two natural numbers and is forced to return a natural number, so often can't return the right answer. For example 5 / 2 = 2 with the division you're using. Computer scientists call it "division with remainder" and I call it "broken and should never be used". When I'm doing this sort of exercise with my class I always coerce everything to the rationals before I do the division, so the division is mathematical division rather than this pathological function which does not satisfy things like (a / b) * b = a. The fact that this division doesn't obey the rules of normal division is why you can't get the tactics to work. If you coerce everything to the rationals before doing the division then you won't get into this mess and ring will work fine.

    If you do want to persevere down the natural division road then one approach would be to start doing things proving that n(n+1) is always even, so that you can deduce n(n+1)/2)*2=n(n+1). Alternatively you could avoid this by observing that to show A/2=B/2 it suffices to prove that A=B. But either way you'll have to do a few lines of manual fiddling because you're not using mathematical functions, you're using computer science approximations, so mathematical tactics don't work with them.

    Here's what my approach looks like:

    import algebra.big_operators
    
    open_locale big_operators
    
    open finset
    
    def arith_sum (n : ℕ) := ∑ i in range n, (i : ℚ) -- answer is rational
    
    example (n : ℕ) : arith_sum n = n*(n-1)/2 :=
    begin
      unfold arith_sum,
      induction n with d hd,
      { simp },
      { rw [finset.sum_range_succ, hd, nat.succ_eq_add_one],
        push_cast,
        ring, -- works now
      }
    end