• Support PF! Buy your school textbooks, materials and every day products Here!

Proof by Induction of String exponentiation? (Algorithms)

  • #1

Homework Statement


gK3OG6l.png

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?
 

Attachments

Answers and Replies

  • #2
verty
Homework Helper
2,164
198
Let ##\alpha## be however long, it doesn't matter. Use induction on n.
 
  • #3
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 = |αn| = |α0| = |λ| = 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| = n|α|

INDUCTION STEP: Suppose n = k + 1. THEN

LHS = |αn| = |α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 = k0 + k1 + ... + kn. 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.
 
  • #4
verty
Homework Helper
2,164
198
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.
 
  • #5
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 = |αn| = |α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?
 
  • #6
verty
Homework Helper
2,164
198
It looks good to me. Well done.
 

Related Threads on Proof by Induction of String exponentiation? (Algorithms)

  • Last Post
Replies
4
Views
1K
Replies
1
Views
286
  • Last Post
Replies
9
Views
2K
Replies
3
Views
10K
Replies
3
Views
4K
Replies
1
Views
873
Replies
3
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
697
  • Last Post
Replies
5
Views
879
Top