Wherein α is a string, λ = ∅ = the empty string, and T* is the set of all strings in the Alphabet T.
(exp-Recursive-Clause 1) : α0 = λ
(exp-Recursive-Clause 2) : αn+1 = (αn) ⋅ α
The Attempt at a Solution
This one is proving difficult for me. I remember my professor mentioning during lecture that usually when you're asked to prove something involving strings, the way to do it is by induction on the length of the string, and given the fact that we're being asked to prove that
(∀n ∈ ℕ)(∀α ∈ T*)(|αn| = n|α|)
the (|αn| = n|α|) bit tells me that induction on the length of α is involved, but I don't see how. Just out of curiosity, I tried it the way I usually do it:
Which isn't right. If I start on the LHS, I've gotPROOF of (∀n ∈ ℕ)(∀α ∈ T*)(|αn| = n|α|) BY INDUCTION on |α|
BASE CASE: Suppose |α| = 0. Then α = λ and
RHS = n|α| = n(0) = 0 ≠ LHS
And that's as far as I got, since I don't know what I can do with |αn| knowing only that |α| = 0.LHS = |αn| =
Am I maybe supposed to be doing induction on n instead of |α|? Or is there something else I'm missing?
26.2 KB Views: 461