[Agda] Matching problem at end of equational reasoning proof
Christoph Herrmann
ch at cs.st-andrews.ac.uk
Wed May 27 17:26:09 CEST 2009
Hi,
I have attached an inductive proof (attempt) of Gauss' summation formula.
The problem is that at the end of the equational reasoning the matching
with the right-hand side of the type does not seem to work, namely:
(suc n) * ((suc n) + 1) against (a * (a + 1)) in the case that a=(suc n)
I am wondering whether Agda still knows that it is in the case a=(suc n)
or whether this information is available only for matching the left-hand
side.
The error message is:
Gauss.agda:42,4-43,3
n + 1 != n of type ℕ
when checking that the expression (suc n * (suc n + 1) ∎) has type
.Relation.Binary.PreorderReasoning._IsRelatedTo_
(.Relation.Binary.EqReasoning._.preorder Data.Nat.setoid)
(suc (n + (n + 1) * suc n)) (_49 n)
Cheers
-------------- next part --------------
module Gauss where
open import Algebra
open import Data.Nat
open import Data.Nat.Properties
import Relation.Binary.EqReasoning
open Relation.Binary.EqReasoning (Data.Nat.setoid)
open import Relation.Binary.PropositionalEquality using (cong)
open Algebra.CommutativeSemiring commutativeSemiring
hiding (_+_; _*_)
renaming (zero to *-zero)
sum : ℕ -> ℕ
sum 0 = 0
sum (suc n) = suc n + sum n
gauss-formula : ∀ {a : ℕ} -> (2 * sum a ≈ a * (a + 1))
gauss-formula {0} =
begin
2 * sum 0
≈⟨ cong (λ p → 2 * p) refl ⟩
2 * 0
≈⟨ refl ⟩
0 * (0 + 1)
∎
gauss-formula {suc n} =
begin
2 * sum (suc n)
≈⟨ cong (λ p → 2 * p) refl ⟩
2 * (suc n + sum n)
≈⟨ refl ⟩
2 * suc n + 2 * sum n
≈⟨ cong (λ p -> 2 * suc n + p) (gauss-formula {n}) ⟩
2 * suc n + (n * (n + 1))
≈⟨ refl ⟩
2 * (n + 1) + n * (n + 1)
≈⟨ refl ⟩
(2 + n) * (n + 1)
≈⟨ refl ⟩
((suc n) + 1) * (suc n)
≈⟨ refl ⟩
(suc n) * ((suc n) + 1)
∎
More information about the Agda
mailing list