- #1

- 29

- 2

## Homework Statement

Wherein α is a string, λ = ∅ = the empty string, and T* is the set of all strings in the Alphabet T.

## Homework Equations

(exp-Recursive-Clause 1) : α

^{0}= λ

(exp-Recursive-Clause 2) : α

^{n+1}= (α

^{n}) ⋅ α

## The Attempt at a Solution

[/B]

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:

PROOF of (∀n ∈ ℕ)(∀α ∈ T*)(|α^{n}| = n|α|) BY INDUCTION on |α|

BASE CASE: Suppose |α| = 0. Then α = λ and

RHS = n|α| = n(0) = 0 ≠ LHS

Which isn't right. If I start on the LHS, I've got

LHS = |α^{n}| =

And that's as far as I got, since I don't know what I can do with |α

^{n}| knowing only that |α| = 0.

Am I maybe supposed to be doing induction on n instead of |α|? Or is there something else I'm missing?