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
0
votes
2 answers

How to describe an inductively defined set?

I have a set $Y \subseteq \Bbb N$, which is defined as: $1 \in Y$ If $n \in Y$ then $(k + 5) \in Y$ and $(k + 9) \in Y$ I am trying to determine how I would go about giving a 'complete description of the set $Y$'. I am not entirely sure what is…
Laura
  • 1
0
votes
0 answers

Tips for Mathematical induction, im student

As much as I try not to do even the most basic demonstration by induction, do you know any way in which I can better understand how to do it, some steps or rules that help me guide me to do them?
Miguel Angel Bernal Sanchez
  • 3
0
votes
1 answer

Induction on an if-then statement

So we are told to do induction on this statement: "Let P(n) be the statement: If a + n = c + n, then a = b.", and I am told to induct on n, so I do. Base: Let P(0) be the statement : "If a + 0 = c + 0, then a = b". which is true. From there, you…
Joesteffy
  • 37
0
votes
0 answers

Mathematical induction: $f_{2n+1}=f^2_{n+1}+f^2_n$

What did I do wrong in the proof by mathematical induction of $f_{2n+1}=f^2_{n+1}+f^2_n$?
WinstonCherf
  • 1,022
0
votes
1 answer

Using structural induction to prove a property of full binary trees

I'm trying to prove $i(T) = \frac{n(T)-1}{2}$ in a full binary tree where $i(T)$ is the number of the internal nodes (Nodes that don't have leaves) and $n(T)$ is the total number of nodes. My base case is a full binary tree with 1 node as it would…
Isk Kander
  • 13
0
votes
7 answers

Proof by induction $6\mid n^3+5n$

$6\mid n^3+5n$ $6\mid (n+1)^3+5(n + 1)= 6k+ 3(n^2+n+2)= 6k + 3(n(n+1)+2) =6m$ I don't understand why this term $n(n+1)+2$ is always divisible by $2$. Can someone please explain it to me?
continuity
  • 111
0
votes
1 answer

Is my answer correct? I came up with this by following an example.

Describe the set of strings that belong to the set A defined recursively as follows BASIC STEP: λ ∈ A, 1 ∈ A RECURSIVE STEP: If x ∈ A then 0x ∈ A and x0 ∈ A. A is the set of all strings over alphabet {0, 1} that are consituted by a sequence of zeros…
Asfandyar Abbasi
  • 3
0
votes
1 answer

Mathematical Induction Question - forgetting a simple rule?

I'm working on a mathematical induction problem for a Computer Science class and I'm trying to solve: a. $$\frac{3(5^{k+1}-1)}{4} + 3(5^{k+1})$$ and I'm getting stuck at: b. $$\frac{3(5^{k+1}-1+4 \cdot 5^{k+1})}{4}$$ I need to get to: c.…
Tukanuk
  • 121
0
votes
1 answer

Prove by induction with powers

I need to prove that $$\frac{1}{\left(2^k\right)^a}+\frac{1}{\left(2^k+1\right)^a}+\frac{1}{\left(2^k+2\right)^a}+\dots+\frac{1}{\left(2^{k+1}-1\right)^a}\le \left(\frac{1}{2^{a-1}}\right)^k$$ for $k\ge1, a \gt 1$. I get stuck after the induction…
McLovin
  • 550
0
votes
3 answers

Induction Proof: $(x+1)^n > nx^2+1$

Prove the following statement using induction. If $x > 1$ is a real number, then $(x+1)^n > nx^2+1$ for all $n \ge 3$.
JBreal1
  • 19
0
votes
0 answers

Inequality proof by induction(?)

I'm trying to prove the following inequality for $a$, $b$ $\in \mathbb{R}_{>0}$, $n$ $\in \mathbb{Z}_+$ $(a + b)^{\frac{1}{n}} \leq a^{\frac{1}{n}} + b^{\frac{1}{n}}$ At first glance I thought this would be provable by induction but had little luck…
ottizy
  • 13
0
votes
0 answers

Proof by induction with a set

I need to prove I formula by induction, but I don't know how to do it. The problem is : Given a set S, prove by induction ∀X·X∈F(S)⇒(∀Y ·Y ∈F(S)⇒card(X×Y)=card(X)∗card(Y)) How should I start?
Antoine Grandchamp
  • 123
0
votes
2 answers

Induction step completion

I am confused how to go about the inductive step of the this given problem.. For all natural numbers $n, 2+4+6+....+2n =(n^2+n)$ I got the base case but now I am confused. Any help is greatly appreciated! Proof: We proceed by induction. …
user503376
0
votes
3 answers

Proof by induction: $n^2<4^n$ $n \in \mathbb N$

i need to proof on induction this questions: $n^2<4^n$ $n \in \mathbb N$ i start with the basic $n=1$ $1^2<4^1$ then put $n=k$ $k^2<4^k$ then if $p(k)=T$ so $p(k+1)=T$ $(k+1)^2<4^{k+1}$ $k^2+2k+1<4^k\cdot 4$ by the indcution $k^2 <…
yogin yogin
  • 27
0
votes
1 answer

Help with Mathematical Proof by induction

I have been asked to prove that: $$ \frac{1}{3*4} +\frac{1}{4*5} +\frac{1}{5*6}+...+\frac{1}{(n+2)(n+3)}=\frac{n}{3(n+3)} $$ Here is what I have so far but cannot work out how to go further. RTP: $$ \frac{1}{3*4} +\frac{1}{4*5}…
Luke Marsden
  • 11
1 2 3
…
99 100