Question on a proof by induction

  • Thread starter mnb96
  • Start date
  • #1
mnb96
715
5
Hello,
I have a subgroup [itex]S=\left\langle A \right\rangle[/itex] generated by the set A, i.e. [itex]S=\left\{ a_1 a_2 \ldots a_n \;|\; a_i \in A \right\}[/itex].

When I need to prove by induction on n some property of S, what should I choose as the base case of induction? n=1, or simply n=0 ?

If the answer is n=0, then it seems to me that in most cases associated with "subgroups generated by some set", we always have to define n=0 as corresponding to the identity element, thus the basis of induction will be always about proving that some property holds for the identity element. Am I right?
 

Answers and Replies

  • #2
Erland
Science Advisor
741
138
Well, I would say that this depends upon how the statement to be proved is formulated. If it says that it should hold for all n>=0, then your interpretation is correct in my opinion. If it should hold only for all n>=1, the problem does not occur.
 
  • #3
SteveL27
799
7
Hello,
I have a subgroup [itex]S=\left\langle A \right\rangle[/itex] generated by the set A, i.e. [itex]S=\left\{ a_1 a_2 \ldots a_n \;|\; a_i \in A \right\}[/itex].

When I need to prove by induction on n some property of S, what should I choose as the base case of induction? n=1, or simply n=0 ?

If the answer is n=0, then it seems to me that in most cases associated with "subgroups generated by some set", we always have to define n=0 as corresponding to the identity element, thus the basis of induction will be always about proving that some property holds for the identity element. Am I right?

Proofs such as you've described typically involve induction on the length of the expression. For example if a group is Abelian, meaning ab = ba, you can use induction to show that you can freely permute the factors of a product of n elements.

Without more info it's difficult to answer your question. In the most general case you can start an induction anywhere.
 

Suggested for: Question on a proof by induction

Replies
1
Views
346
Replies
21
Views
350
  • Last Post
Replies
12
Views
353
  • Last Post
Replies
5
Views
600
  • Last Post
Replies
21
Views
791
  • Last Post
Replies
4
Views
665
  • Last Post
Replies
17
Views
701
Replies
5
Views
1K
  • Last Post
Replies
17
Views
537
Replies
4
Views
443
Top