证明从递归定义的函数返回的列表在 Coq 中是固定长度的

Question

如何证明如下引理：

Require Import Coq.Lists.List.

Lemma len_seq_n : forall start n, length (seq start n)=n.

我试过了

Proof.
induction n.
simpl. auto. simpl.

此时 Coq 给了我

1 subgoal
start, n : nat
IHn : length (seq start n) = n
______________________________________(1/1)
S (length (seq (S start) n)) = S n

我不确定如何从那里继续。

Answer 1

问题是你的归纳假设不够普遍。您需要改为使用以下语句：

IHn : forall start', length (seq start' n) = n

为了获得这个假设，在使用 revert 策略对 n 进行归纳之前，简单地概括 start。

Proof.
  intros start n.
  revert start.
  induction n.
  (* Continue as previously *)

（下次请提供完整的例子，以便我们更好地帮助您。您的问题缺少seq的定义。）

prove that a list returned from a recursively defined function is fixed length in Coq