Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question on a proof by induction

  1. Sep 30, 2012 #1
    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?
     
  2. jcsd
  3. Oct 1, 2012 #2

    Erland

    User Avatar
    Science Advisor

    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.
     
  4. Oct 1, 2012 #3
    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook