Learn Build finite objects, choose induction hypotheses, prove recursive functions correct and distinguish a generated word from its construction. Written arguments need review; finite traces do not establish a universal theorem.
Open any lesson. Completion records participation; automatic practice checks and human judgment of written arguments are separate. This unit retains its own versioned requirements.
Try these short questions on paper, then compare your reasoning. They are optional self-checks, not a placement score or a navigation requirement. Use a targeted review when useful and return with your browser’s Back control.
A recursive object can have several smaller children, each needing its own hypothesis.
Prove the base cases, then assume the claim for the smaller inputs used by a constructor and prove it for the resulting object. Finite examples cannot replace a general step.
Generated words must be compared in both directions.
Prove every object generated by the first description satisfies the second, and that every object satisfying the second can be generated by the first.
Loading saved mathematics work…
Unfamiliar constructions and recursive proofs
The mixed assessment has separate response history and review criteria; it does not change lesson participation records.
Each linked lesson opens on its own page. Expand its details here when you want to check the objectives before choosing.
Define finite ordered full binary trees, compute counts recursively and prove a statement for every permitted construction.
6 practice tasks.
Trace finite tree recursion, prove a mirror law and a sharp leaf bound, and generalize a word-reversal invariant when a weak induction hypothesis fails.
8 practice tasks.
Prove that a recursive grammar describes exactly the balanced parenthesis words, then use unique first-return parsing to justify recursive definitions.
6 practice tasks.