## Welcome to Mathematics Educators Stack Exchange

Mathematics Educators Stack Exchange is a question and answer site for those involved in the field of teaching mathematics. It's built and run by you as part of the Stack Exchange network of Q&A sites. With your help, we're working together to build a library of detailed answers to every question about teaching mathematics.

We're a little bit different from other sites. Here's how:

This site is all about getting answers. It's not a discussion forum. There's no chit-chat.

Just questions...

up vote

Good answers are voted up and rise to the top.

The best answers show up first so that they are always easy to find.

accept

Accepting doesn't mean it's the best answer, it just means that it worked for the person who asked.

# 'Low-algebra' examples of induction

What are good examples of proofs by induction that are relatively low on algebra? Examples might include simple results about graphs.

My aim is to help students get a sense of the logical form of an induction proof (in particular proving a statement of the form 'if $P(k)$ then $P(k+1)$'), independent of the way one might show that in a proof about series formulae specifically.

How about the Tower of Hanoi puzzle and finding the optimal number of moves?

This link describes the recursive solution procedure and a proof of optimality using induction.

https://proofwiki.org/wiki/Tower_of_Hanoi

How about: A tree with $n\ge 1$ vertices has $n-1$ edges.

## Get answers to practical, detailed questions

Focus on questions about an actual problem you have faced. Include details about what you have tried and exactly what you are trying to do.

• Specific issues with teaching mathematics
• Real problems or questions that you’ve encountered

Not all questions work well in our format. Avoid questions that are primarily opinion-based, or that are likely to generate discussion rather than answers.

Questions that need improvement may be closed until someone fixes them.

• Anything not directly related to teaching mathematics
• Questions that are primarily opinion-based
• Questions with too many possible answers or that would require an extremely long answer

## Tags make it easy to find interesting questions

All questions are tagged with their subject areas. Each can have up to 5 tags, since a question might be related to several subjects.

Click any tag to see a list of questions with that tag, or go to the tag list to browse for topics that interest you.

# 'Low-algebra' examples of induction

What are good examples of proofs by induction that are relatively low on algebra? Examples might include simple results about graphs.

My aim is to help students get a sense of the logical form of an induction proof (in particular proving a statement of the form 'if $P(k)$ then $P(k+1)$'), independent of the way one might show that in a proof about series formulae specifically.

## You earn reputation when people vote on your posts

+5 question voted up
+2 edit approved

As you earn reputation, you'll unlock new privileges like the ability to vote, comment, and even edit other people's posts.

Reputation Privilege
15 Vote up
125 Vote down (costs 1 rep on answers)

At the highest levels, you'll have access to special moderation tools. You'll be able to work alongside our community moderators to keep the site focused and helpful.

500 Vote to close, reopen, or migrate questions Edit other people's posts Access to moderation tools
see all privileges

## Improve posts by editing or commenting

Our goal is to have the best answers to every question, so if you see questions or answers that can be improved, you can edit them.

Use edits to fix mistakes, improve formatting, or clarify the meaning of a post.

You can always comment on your own questions and answers. Once you earn 50 reputation, you can comment on anybody's post.

Remember: we're all here to learn, so be friendly and helpful!

How about the Tower of Hanoi puzzle and finding the optimal number of moves?

This link describes the recursive solution procedure and a proof of optimality using induction.

https://proofwiki.org/wiki/Tower_of_Hanoi

I really like this idea as a lesson plan. Start the class out by just introducing the rules and playing a game with 3 disks. Ask them the find the fewest moves. Then after they are confident in moving three pieces around, give every group a 4th piece and ask for the fewest number of moves again. Hopefully most of them will stumble onto the fact that once they move one of the pieces out of the way, they have 'reduced' the n=4 case into the n=3 case, which they know how to handle. Then give them n=5 and n=6 to see if they can build on their knowledge of n=3 and n=4. - ruferd Sep 18 at 12:45

## Unlock badges for special achievements

Badges are special achievements you earn for participating on the site. They come in three levels: bronze, silver, and gold.

 Informed Read the entire tour page
 Student First question with score of 1 or more Editor First edit Good Answer Answer score of 25 or more Civic Duty Vote 300 or more times Famous Question Question with 10,000 views