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
1 answer

True or Flawed proof

Is the following proof correct or flawed? (a) Claim: For every positive integer $n, n^2 + 3n$ is odd. Proof: The proof will be by induction on $n$. Base Case: The number $n = 1$ is odd. Induction Hypothesis: Assume that $k^2 + 3k$ is odd, for some…
user3434743
  • 393
0
votes
1 answer

Prove by induction that $7^n < n!$ for all integer $n \ge 21$

Prove by induction that $7^n < n!\,$ for all integers $n\ge 21$
Amirpasha
  • 49
0
votes
1 answer

How to prove the exponent law with rational exponents by Induction

May I know how to prove that $b^n \times b^m = b^{n+m}$ given that the exponents are now rational numbers instead of pure integers ?
Alan
  • 1
0
votes
1 answer

Prove by mathematical induction

I stuck with a problem like this. I know all the steps but I can't prove that it is true when n=k+1. n^2 ≥ 2n + 1, for all n ∈ N such that n ≥ 3.
Gummy
  • 31
0
votes
1 answer

Stuck at this induction problem

I am giving it everything, but i just can't get it right. The problem: Prove by induction that $n!>2^n$ for all integers $n\ge4$ I know how to solve the basic induction problems, but no matter what I do, I can't get this one right. I saw how the…
mythic
  • 137
0
votes
1 answer

Show for any integer $k \geq 1$ can be uniquely expressed as $k = 2^x + i2^{x+1}$

Show for any integer $k \geq 1$ can be uniquely expressed as $k = 2^x + i2^{x+1}$ for $i,x \geq 0$ and $i,x \in \mathbb{N}$ My attempt was to prove it inductively: $k = 1$, true assume true for $k = n$ i.e. $n = 2^x + i2^{x+1}$ then we know $k+1$ is…
Lekx33
  • 1
0
votes
3 answers

Proof formula with induction

How can I prove by induction that $\forall n\in\mathbb{N}: \ 3^{2n} - 1$ is divisible by $8$. Proof for $n=1$: $\displaystyle3^{2\cdot1} - 1 = 8$ which is divisible by $8$. How can I prove it for $n+1$? this is where I got so far: $3^{2(n+1)} - 1 =…
D_R
  • 987
0
votes
1 answer

Find a formula for... (Induction and Recursion)

a)Find a formula for $$\frac 1 2 + \frac 1 4 + \frac 1 8 + \cdots + \frac1{2^n}$$ by examining the values of this expression for small values of $n$. b) Prove the formula you conjectured in part a. If you can help me with part a, I would really…
Ayechan_San
  • 357
0
votes
2 answers

Prove by Induction: $n \le 3 \sqrt{n} +4$. How to work with the Square-root?

I want to prove the statement $$n \le 3 \sqrt{n} +4$$ for every $n$ belongs to $N$ by induction. So what I have done so far is proving for $p(1)$ is true and assuming that $p(n)$ is true. Now, I want to prove that $p(n+1)$ is also true; $$n+1 \le 3…
FarahFai
  • 161
  • 9
0
votes
2 answers

Use induction to show that $f(n)=2\log_2n+1$

Given is that $$f_n=f_{n/2}+2$$ $n=2^k$ $k=1,2,3...$ and $f(1)=1$ use induction to show that $f(n)=2\log_2n+1$ how do i use induction to solve this?
emma
  • 297
0
votes
1 answer

Coming up with an alternative proof by induction

Kindly refer to Q4 of this handout. "$2n$ dots are placed around the outside of the circle. $n$ of them are colored red and the remaining $n$ are colored blue. Going around the circle clockwise, you keep a count of how many red and blue dots you…
hoogepooge
  • 3
  • 1
  • 3
0
votes
1 answer

Show by induction whether $1+\frac{1}{2}+\frac{1}{3}\cdots+\frac{1}{n}$ is an integer or not

How can I show by induction whether $1+\frac{1}{2}+\frac{1}{3}\cdots+\frac{1}{n}$ is an integer or not? Progress : For n=1 the expression is $(=1)$ an integer. How can I show the next step?
Smart Math
  • 11
  • 1
  • 1
0
votes
5 answers

Prove by Induction $64\mid (7^{2n} + 16n − 1)$

We have to show by Mathematical Induction that $64\mid (7^{2n} + 16n − 1).$ Progress : Let us suppose $P(n)$ be the statement i.e., $P(n): 64\mid(7^{2n} + 16n − 1)$ For $n=1$, $(7^{2\cdot 1} + 16\cdot 1 − 1=64$ which is divisible by $64$. …
Smart Math
  • 11
  • 1
  • 1
0
votes
1 answer

Prove that this is true

$$\sum\limits_{i=1}^{n}i^x = P_{x+1}(n)$$ Let x be any nonnegative integer and show that there is a polynomial $P_{x+1}$ of degree $x+1$ for every $n$ greater than or equal to $1$.
user181415
  • 39
  • 7
0
votes
2 answers

An induction question on showing that eventually $(n+2)^n < (n+1)^{n+1}$

Show that eventually $(n+2)^n < (n+1)^{n+1}$ I can see that this is obvious by evaluation at n>2, but I am having a hard time separating to get the induction step within the parenthesis. I am sorry if this is too easy a problem. Or, maybe there's…
user102830
  • 93
1 2 3
…
99 100