Proof by Induction of String exponentiation? (Algorithms)

[Enharmonics]

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) : α⁰ = λ
(exp-Recursive-Clause 2) : αⁿ⁺¹ = (αⁿ) ⋅ α

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|α|)

the (|αⁿ| = 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|α|) 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 = |αⁿ| =

And that's as far as I got, since I don't know what I can do with |αⁿ| knowing only that |α| = 0.

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

 

[verty]

Let $\alpha$ be however long, it doesn't matter. Use induction on n.

 

[Enharmonics]

Let $\alpha$ be however long, it doesn't matter. Use induction on n.

After a few hours of trying, I managed to make it through the synthetic method using induction on n and another proposition (I'll call it "Length of Concatenated Strings", that was proven in class:

PROPOSITION 1: LENGTH OF CONCATENATED STRINGS
∀α, β |α ⋅ β| = |α| + |β|

So here's the base case:

BASE CASE: Suppose n = 0, α is an arbitrary string. Then

LHS = |αⁿ| = |α⁰| = |λ| = 0 = 0|α| = n|α| = RHS

I'll pause here to note that I'm not confident this is right; in fact, I suspect it's wrong. This particular sequence of steps where I go from
the length of the empty string |λ| (which is 0 by definition) to n|α|:

|λ| = 0 = 0|α| = n|α|

Is one I didn't really "believe" while I was writing (but I kept going because I wanted to at least feel like I was making some progress). My reasoning is that 0 = 0|α|, since the length of a string |α| ε ℕ and therefore 0|α| = 0 due to the multiplication property of 0. Then, since I established in the premise of the base case that n = 0, I substitute 0|α| = n|α| to "complete" the proof.

I don't know how to explain it, but this seems "finicky" to me. I don't feel that I did it "right". Still, I continued to the inductive step, again just wanting to feel like I was making some headway:

INDUCTION HYPOTHESIS: If n = k, then |αⁿ| = n|α|

INDUCTION STEP: Suppose n = k + 1. THEN

LHS = |αⁿ| = |α^{k + 1}| = |(α^k) ⋅ α| = |k|a| ⋅ a| = k|α| + |α| = (k+1)|a| = n|a| = RHS

Again, I don't "feel" that this many of these steps are right. In particular:

|k|α| ⋅ α| = k|α| + |α|

Based on PROPOSITION 1, |k|α| ⋅ α| actually yields |k|α|| + |α|, but I reasoned that

|k|α|| + |α| = k|α| + |α|

Since k ε ℕ and |α| ε ℕ (definition of the length of a string). That is, | k * |α| | should be the same thing as just k * |α|, since neither k nor |α| are strings and length is a property of strings, so the extra | | are superfluous.

This:

k|α| + |α| = (k+1)|α|

is based on the definition of multiplication, i.e. n * k = k₀ + k₁ + ... + k_n. I don't know if I can use it here, though.

Finally, this:

(k+1)|α| = n|α|

This is the iffiest step of all. It's based on the fact that I let n = k + 1 at the beginning of the inductive step, but I'm not sure that I can actually use that anymore once I've already transformed that k + 1 into a k in the step

|α^{k + 1}| = |(α^k) ⋅ α|

Anyhow, that's what I've got so far. Apologies if my questions seem stupid. This is my first time practicing induction in a very long time. I'd appreciate it if you (or anyone else) could let me know if I'm on the right track with this answer, or point me in the right direction if I'm not.

 

[verty]

One thing I see is I didn't see this step: $|\alpha^k \cdot \alpha| = |\alpha^k| + |\alpha|$. What you did instead was not correct.

 

[Enharmonics]

One thing I see is I didn't see this step: $|\alpha^k \cdot \alpha| = |\alpha^k| + |\alpha|$. What you did instead was not correct.

Thanks! I must've mixed up the order of the steps while desperately trying to figure this out yesterday.

I've revised my inductive step to reflect that fact. Here's the new version:

LHS = |αⁿ| = |α^{k + 1}| = |(α^k) ⋅ α| = |α^k| + |α| = k|α| + |α| = (k+1)|α| = n|α| = RHS

Is this better? Also, is writing

k|α| + |α| = (k+1)|α| = n|α|

Based on the fact that I set n = k + 1 at the beginning of the inductive step correct after all?

 

[verty]

It looks good to me. Well done.