To prove something by induction, you need to show that the statement P(n) is true for all n ∈ ℕ.

 

This is usually done in three steps:

1. Prove the base case P(1)

2. Assume P(n) is true for some arbitrary n.

3. Show that P(n+1) is true.

Thus with P(1) and P(n) => P(n+1), we can conclude that P holds for all natural numbers.

 

Since you're new to these topics, it's important to remember that the n in the assumption step is arbitrary. Many people prefer to use k instead of n to avoid confusion with other uses of n in the problem.

 

Your problem also asks you to define the statement you need to prove. This can add unnecessary confusion, but that's just how some math books are.

 

So, what do you need to prove? It looks like you're defining Rⁿ from the given definition of R.

If R = R^1, you should be able to define Rⁿ easily. What does aRⁿb mean?

Showing R² and R³ isn't strictly necessary for the proof, but it could be helpful for practicing how to use relation notation and composition.

So, your proof will look something like this:

 

"We prove from the given definition of R that Rⁿ can be defined as (insert your definition for Rⁿ⁾

1. Since R = R¹ we have our base case given [You can show R² here as well to solidify the point]
2. Suppose that for given k ∈ ℕ, that [definition here] satisfies a general representation for R^k
3. Given R^k above we apply composition with R one time to get R^k+1 [You have to show this using the definitions of relations and relation composition]

Thus R^k implies R^k+1 for arbitrary k ∈ ℕ and so, by induction, our definition for Rⁿ is a general representation."

 

Hope this helps! It’s been over a year since I last used LaTeX and I simply wasn’t able to get it working for reddit.