Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [induction]

For questions about mathematical induction, a method of mathematical proof. Mathematical induction generally proceeds by proving a statement for some integer, called the base case, and then proving that if it holds for one integer then it holds for the next integer. This tag is primarily meant for questions about induction over natural numbers but is also appropriate for other kinds of induction such as transfinite, structural, double, backwards, etc.

Mathematical induction is a form of deductive reasoning. Its most common use is induction over well-ordered sets, such as natural numbers or ordinals. While induction can be expanded to class relations which are well-founded, this tag is aimed mostly at questions about induction over natural numbers.

In general use, induction means inference from the particular to the general. This is used in terms such as inductive reasoning, which involves making an inference about the unknown based on some known sample. Mathematical induction is not true induction in this sense, but is rather a form of proof.

Induction over the natural numbers generally proceeds with a base case and an inductive step:

  • First prove the statement for the base case, which is usually $n=0$ or $n=1$.
  • Next, assume that the statement is true for an input $n$, and prove that it is true for the input $n+1$.

The following variant goes without a base case: Assuming the statement is true for all $n\in\mathbb N$ with $n < N$, prove that is true for $N$, too. This has to be done for all $N\in\mathbb N$.

10150 questions
1
vote
1 answer

Round robin algorithm proof

I need to prove by induction the theorem that says we can construct a round robin tournament: Given a tournament with $2^k$ teams. We label the teams $t_1, t_2, ..., t_{2^k}$. It is possible to construct $2^k -1$ rounds of $2^{k-1}$ games where each…
gberger
  • 123
1
vote
1 answer

Proof by induction question about fuel depots

You are asked to drive a lunar rover around the moon (which is just a circle in this question). There are (finitely many) fuel depots on the way, with the total amount of fuel stored in them enough to get around the moon exactly once. Show that…
Superbus
  • 2,136
1
vote
2 answers

Mathematical Induction for divisibility by $7$

Not entirely sure if this is where I should post, but I need help. I need to prove $7\mid (9^n - 2^n)$ for all $n\ge 1$. I have the parts for $n = 1$. But when it comes to solving $k \implies k+1$, I run into issues. I get that $(9^k - 2^k) = 7a$.…
latenighthelp
  • 11
1
vote
2 answers

How does mutual induction work?

In my understanding you use the Induction Hypothesis to back up your argument, but what doesn't make sense to me is that we use the Induction Hypothesis even though the Induction Hypothesis wasn't proven yet! How does that make any sense? The…
george
  • 23
1
vote
3 answers

Prove that for all $n$ in the natural numbers, $n(n - 1) < 2^n$

This seems like a fairly easy induction problem but I am a bit rusty. I have the first two steps -- that the statement holds for $n = 1$, and I am assuming that for $n = k$, $k(k - 1) < 2^k$. Now for showing it holds for $n = k + 1$: $$(k + 1)(k + 1…
Matt Nashra
  • 1,245
1
vote
5 answers

Prove for which $n \in \mathbb{N}$: $9n^3 - 3 ≤ 8^n$

A homework assignment requires me to find out and prove using induction for which $n ≥ 0$ $9n^3 - 3 ≤ 8^n$ and I have conducted multiple approaches and consulted multiple people and other resources with limited success. I appreciate any hint you can…
Florian Mayer
  • 113
1
vote
3 answers

proving golden ration with induction

If $\displaystyle a=\frac{1+\sqrt{5}}{2}$ and $\displaystyle b=\frac{1-\sqrt{5}}{2}$, prove that $\displaystyle f_n=\frac{a^n-b^n}{\sqrt{5}}$ for all $n\in\mathbb{P}$ Would we start with a base case for proof of induction? In that case, $n=0$ would…
cooltrainer
  • 105
1
vote
4 answers

Principle of mathematical induction problem

Prove the inequality $4^{2n}>15n$ For $n = 1$, $4^{2\cdot1}=16>15\cdot1$ Let us assume it is true for $n=k$ $4^{2k}>15k$
student
  • 11
1
vote
1 answer

Proof by induction: $2^n > n$

Base is $2^1 > 1$. Now we assume $2^n > n$ and try to obtain $2^{n+1} > (n+1)$. If I can use $2^n > 1$, I could just add that to $2^n > n$ and get $2^{n+1} > (n+1)$ but I don't know how to obtain the form $2^n > 1$ in order to use it. Is there a…
mr eyeglasses
  • 5,539
1
vote
1 answer

Proof by induction for an unknown function, e.g. $\frac{\sum_{k=0}^n (k-1)\cdot (n-k-1)}{n^2} = \frac{n}{6} - \frac{1}{6n}$

I get how to do a proof by induction for say, a sum of all numbers or a sum of all numbers^2 function. But where do I start with a problem like: $$\frac{\sum_{k=0}^n (k-1)\cdot (n-k-1)}{n^2} = \frac{n}{6} - \frac{1}{6n}$$ So the function is…
MeltyButter
  • 113
1
vote
1 answer

Prove that $P(n)$ can be proven by strong induction if and only if it can be proven by regular induction.

If $P(n)$ can be proven by strong induction, I know we can strengthen the inductive hypothesis to prove it by regular induction, right? But how would I do this?
atherton
  • 1,234
1
vote
1 answer

Inductive Specification on a String

To make things clear, I'll give the question as it was given to me. The explanation I've been given by my lecturer wasn't clear to me, and Google has not helped thus far. Considering the following inductive specification of strings: S ::= ε |…
hiddensunset4
  • 153
1
vote
4 answers

Prove that for all $n \in \mathbb{N}$: $2^{n-1}(a^n + b^n) \ge (a + b)^n$

Prove that for all $n \in \mathbb{N}$: $$2^{n-1}(a^n + b^n) \ge (a + b)^n$$ I used induction (for $k = 1,2,...n-1$), and ended up with the following equation: $$(a + b)(a + b)^{n-1} \le (a + b)(a^{n-1} + b^{n-1})2^{n-2}$$ Now, I have a feeling I'm…
zachary
  • 11
1
vote
3 answers

Induction problem: "if the group has at least one player who is better than Messi, then all the members of the group are better than Messi"

I'm having some trouble with the following problem: "A french man is trying to prove that any non empty group of french soccer players satisfies the following: 'if the group has at least one player who is better than Messi, then all the members of…
Amanjo
  • 117
1
vote
2 answers

proof by strong induction of single variable with exponent

$x^n + \frac{1}{x^n} \in \mathbb{Z}$ (is an integer), for all positive integers $n$, where $x$ is rational. I've surmised that the only rational numbers that satisfy $x$ are 1 and -1. Thus, as you grow in size with $n$, the answer will always either…
compguy24
  • 421
1 2 3
…
99 100