Question on a proof by induction

  • Thread starter mnb96
  • Start date
  • #1
713
5

Main Question or Discussion Point

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
738
136
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
795
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.
 

Related Threads on Question on a proof by induction

  • Last Post
Replies
7
Views
4K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
7
Views
4K
Replies
1
Views
3K
  • Last Post
Replies
3
Views
2K
Replies
6
Views
22K
Replies
23
Views
8K
  • Last Post
Replies
1
Views
2K
Top