proposition: Theorem RndNat_seq : forall (n : posnat)(A : Set)(c : nat -> Comp A) a, evalDist (x <-$ RndNat n; c x) a == (1 / n) * sumList (allNatsLt n) (fun z => evalDist (c z) a).
proof: Proof. intuition. rewrite evalDist_seq_step. eapply eqRat_trans. eapply sumList_body_eq. intros. eapply ratMult_eqRat_compat. eapply RndNat_prob. eapply RndNat_support_lt. trivial. eapply eqRat_refl. rewrite sumList_factor_constant_l. eapply ratMult_eqRat_compat; intuition. eapply sumList_permutation. eapply NoDup_Permutation. eapply getSupport_NoDup. eapply allNatsLt_NoDup. intuition. eapply allNatsLt_lt_if. eapply RndNat_support_lt. trivial. eapply in_getSupport_RndNat. eapply allNatsLt_lt. trivial. Qed.
imports: FCF.Crypto Permutation FCF.NotationV1