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 ...

learn more… | top users | synonyms

4
votes
3answers
218 views

Puzzle: “Yes colour of my hat is white.”

There are $n$ people in room each being put on hat from amongest at least $n$ white hats and $n-1$ black hats. They stand in a queue, so that everyone can see the colour of the hat of the person ...
1
vote
1answer
50 views

Proof of sum of binomials over upper index (induction)

How would you proof $$ \sum_{m=k}^{n}\binom{m}{k} = \binom{n + 1}{k + 1} $$ with $n \geq k$ and $n$, $k \in \mathbb{N}$ by induction? I had some approaches but wasn't sure if they were right, so I'd ...
2
votes
2answers
43 views

Mathematical Induction Angles proof.

![this is a very dicy problem. It would be great to go into details of how to prove it using induction or any other alternate way is highly appreciated.][1] ...
1
vote
1answer
30 views

Finding $\sup$ and $\inf$ of $\{\frac{nk}{1+2n+3k} : n,k \in \Bbb{N}\}$

I'm trying to solve the following problem: Find $\sup$ and $\inf$ of $A=\{\frac{nk}{1+2n+3k} : n,k \in \Bbb{N}\}$ and maximal and minimal element of this set. As for $\sup(A)$ and $\max(A)$ I tried ...
0
votes
3answers
47 views

A Problem involving simple mathematical induction.

$6^n-5n+4$ is divisible by $5 \;$ for all natural numbers $n$. what I did is: IA $A(1):\;6^1-5\cdot1+4=5$ which is true. IS $A(n):\; 6^n+5n+4$ is also divisible by $5$. Show $A(n+1)$ is ...
1
vote
3answers
129 views

Proof of the Principle of mathematical Induction [duplicate]

We always use the Principe of Mathematical induction and we have two versions of it. I myself have been using it for many years. But it just came to my mind that I have never seen a proof of the ...
3
votes
1answer
50 views

Induction proof for a summation: $\sum_{i=1}^n i^3 = \left[\sum_{i=1}^n i\right]^2$ [duplicate]

Prove by induction: $\sum_{i=1}^n i^3 = \left[\sum_{i=1}^n i\right]^2$. Hint: Use $k(k+1)^2 = 2(k+1)\sum i$. Basis: $n = 1$ $\sum_{i=1}^1 i^3 = \left[\sum_{i=1}^1 i\right]^2 \to 1^3 = 1^2 \to 1 = 1$. ...
1
vote
2answers
47 views

Proof by Induction that $16 \mid 5^n - 4n - 1$

Using induction, prove that $16\mid 5^n - 4n - 1$ for $n$ in $\mathbb{N}$ Here's what I have and what I'm stuck on: basis: $n = 1$, $5 - 4(1) - 1 = 0$ and $16\mid 0$. Hypothesis: Assume true for ...
1
vote
0answers
15 views

What method to use to find a hypothesis of the solution of the recurrence relation?

Suppose that we want to find an asymptotic upper bound for a recurrence relation: $T(n)=aT \left ( \frac{n}{b}\right)+f(n)$ , $T(n)=c, \text{ when } n \leq n_0$, using the following method: We choose ...
3
votes
1answer
355 views

Using induction to prove an equality in harmonic numbers

Question: Prove that harmonic numbers satisfy the equality using induction $$ H_{1}+ H_{2} + · · · + H_{n} = (n + 1)H_{n} − n. $$ I have done the basis step: $(1 + 1)H_{1} − 1 = 1$. Correct. Done the ...
0
votes
1answer
45 views

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 ...
1
vote
2answers
43 views

Prove (by induction?): If $A \subset \mathbb{N}$, $4 \in A$ and $n+1 \in A$ whenever $n \in A$, then $\left\{n \mid n \geq 4 \right\} \subset A$.

Prove: If $A \subset \mathbb{N}$, $4 \in A$ and $n+1 \in A$ whenever $n \in A$, then $\left\{n \mid n \geq 4 \right\} \subset A$. So for the base case, I did $n = 4$, so we have $4 \in A$ by ...
0
votes
1answer
55 views

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

Prove by induction that $7^n < n!\,$ for all integers $n\ge 21$
1
vote
2answers
207 views

Proof by induction failure if assumption is wrong?

I never got a clear answer to this question in college. What happens in an induction proof if the assumption is wrong? For example, suppose we try to prove that $n^5$ > n! for n >= $2$ so we start ...
1
vote
4answers
38 views

Prove $(n!)/n^n \leq 1/2^{k}$, where $k$ is the floor of $n/2$.

I suppose the natural way to prove this is by induction. When I follow the rather natural steps $$\frac{(n+1)!}{(n+1)^{n+1}} = \frac{n!}{(n+1)^{n}} \leq \frac{n!}{(n)^{n}}$$ in order to apply the ...
0
votes
1answer
43 views

Proof of series with induction

I have the sum ...
0
votes
1answer
42 views

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 ?
0
votes
1answer
28 views

Prove by induction that $\sum_{i = 1}^{n} \frac{1}{\sqrt{i}} \leq 2\sqrt{n} - 1$

Prove by induction that $\sum_{i = 1}^{n} \frac{1}{\sqrt{i}} \leq 2\sqrt{n} - 1$ I want to do the $n - 1 \rightarrow n$ induction step. But I'm confused as to what my base case is. Usually if I want ...
0
votes
3answers
44 views

Prove that $S_n = 5^n - 1$

Use Strong Induction: $s_0 = 0 $, $s_1 =4$ and $s_n= 6s_{n-1} - 5s_{n-2}$ for all $n\in \mathbb{N} \setminus \{1\}$ Prove that $S_n = 5^n - 1$ In regards to the first step, can I start at n=2? Not ...
0
votes
1answer
34 views

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.
3
votes
6answers
175 views

Prove that if $n^2$ is divided by 3, then also $n$ can also be divided by 3.

$n\in \Bbb N$ Prove that if $n^2$ is divided by 3, then also n can also be divided by 3. I started solving this by induction, but I'm not sure that I'm going in the right direction, any ...
1
vote
3answers
35 views

Proving inequalities using induction all natural numbers that's greater than or equal to 5

using mathematical induction, prove that $n\le5: 4n<2^n$ base case: $4(5) < 2^5$ $20 < 32$ Correct I need help with the inductive process
3
votes
4answers
84 views

How can I show that $n! \leqslant (\frac{n+1}{2})^n$?

Show that $$n! \leqslant (\frac{n+1}{2})^n \quad \hbox{for all } n \in \mathbb{N}$$ I know that it can be done by induction but I always find line where I do not know what to do next.
0
votes
2answers
36 views

Proof by induction with variable other than $n$ [duplicate]

1) Prove that $(1+x)^{n} \geq 1 + nx$ for every $n \in \mathbb{N}$ and $x \in (-1, \infty)$ Base case: Usually for the base case I just take $n = 1$ but since there's another variable $x$, I wasn't ...
0
votes
2answers
43 views

Prove by induction that $r_0 + r_1a + r_2a^2 + \cdots + r_{n−1}a^{n−1} < a^n$.

Let $a$ be a natural number greater than $1$. Prove that for all integers $r_0 , r_1 , \cdots , r_{n−1}$ with $0 ≤ r_j < a$, we have: $$ r_0 + r_1a + r_2a^2 + \cdots + r_{n−1}a^{n−1} < a^n ...
4
votes
2answers
547 views

Proving that if one person in any group of four knows three, then someone knows everyone.

title can't exactly capture the description of this problem so well. Here's the question in full: "At a convention, any group of four people contains one who knows the other three. Prove there is ...
2
votes
4answers
43 views

Use Induction to prove: $(1+2x)^n \geq 1+2nx$

Show by induction that: for all $x>0$ that $(1+2x)^n \geq 1+2nx$ So far I have: for $n=1 \rightarrow (1+2x)^1 \geq 1+2x$. True! for $n=k+1 \rightarrow (1+2x)^{k+1} \geq 1+2(k+1)x$ ...
0
votes
1answer
54 views

characteristic function differentiation

Let $\mu$ be a probability measure on $\mathbb{R}$. Then the characteristic function is: $$ \varphi: \mathbb{R} \rightarrow \mathbb{C} \;\;\ \varphi(t):=i\int_\mathbb{R} e^{itx}d\mu(x) $$ Prove with ...
2
votes
2answers
128 views

$\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$

Please help! I need help on my assignment for discrete mathematics! Prove the following identity: $\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$ I need to ...
2
votes
2answers
65 views

Prove by mathematical induction that exponentials grow faster than polynomials

How to prove that for $\forall q>1$ $\forall k\in \mathbb{N}$ $\exists c>0$ $\forall \in \mathbb{N}$ $q^n≥cn^k$? I should use mathematical induction.
0
votes
2answers
44 views

Combinatorics identity proof by induction

Prove the formula by induction on n and fixed r: $\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \ldots + \binom{n}{r} = \binom{n+1}{r+1}$ What I tried: Base: we take $n=r$ so $\binom{r}{r} = ...
1
vote
2answers
42 views

Inductive proof of the degree of a polynomial

Here is the problem: Assume that there is a polynomial $P(x)$ of degree 4 such that for all $N \in \mathbb{N}$, $$P(N) = \sum\limits_{n=0}^N n^3$$ Find the polynomial. Use induction to prove that ...
7
votes
2answers
82 views

Function composition: $f^{653}(56)=?$

Let $f(x) = \frac1{(1-x)}$. Define the function $f^r$ to be $f^r(x) = f(f(f(...f(f(x)))))$. Find $f^{653}(56)$. What I've done: I started with r=1,2,3 and noticed the following pattern: $$f^r(x)= ...
2
votes
2answers
48 views

Prove By Induction (Fibonacci Sequence)

Prove by PMI $\gcd(f_n,f_{n+1}) = 1$ for all natural numbers $n$. $f_n$ represents the Fibonacci sequence.
1
vote
2answers
239 views

Number of particles at time $t$

A following problem appears in my text book under the section of induction: At time $0$, a particle resides at the point $0$ on the real line. Within $1$ second, it divides into $2$ particles that ...
1
vote
1answer
185 views

prove weak induction implies strong induction

So trying to prove: i) $[t(n_0)\wedge \forall_n[t(n)\rightarrow t(n+1)]\Rightarrow \forall_{n_0\le n}t(n)]$ $\Rightarrow$ ii) $[s(n_0)\wedge s(n_1)\wedge\cdots \wedge ...
1
vote
0answers
39 views

Game of writing a binary sequence proof

Let $n \gt 2$ be a natural number. We consider the following game. Two players write a sequence of $0$s and $1$s. They start with an empty line and alternate their moves. In each move, a player writes ...
0
votes
1answer
92 views

Using induction for $x^n - 1$ is divisible by $x - 1$

Prove using induction that for all non-negative integers n and for all integers $ x > 1 $, $ x^n - 1 $ is divisible by $ x - 1 $. Step 1: We will prove this using induction on n. Step 2: Assume ...
1
vote
3answers
56 views

Proof that when repeatedly splitting a heap of marbles into two and writing down the product of the two heap sizes, the total is ${x \choose 2}$

Here is the problem in full: A heap has $x$ marbles, where $x$ is a positive integer. The following process is repeated until the heap is broken down into single marbles: choose a heap with more ...
0
votes
3answers
50 views

Proof by Induction: Series of binomial coefficients with same k-length subsets

I have no idea how to prove this binomial equation identity. For reference this is included in Discrete Mathematics for Computer Scientists by Clifford Stein, Robert Drysdale and Kenneth Boggart, ...
0
votes
1answer
36 views

Inductive proof on r

Let $r, n ∈ N$ and let $r ≤ n$. Give an inductive proof for: $$ {n+1 \choose r + 1} = ∑_{k=r}^n {k \choose r} $$ Step 1: We will prove this using induction on n. n = 1 Step 2: n = k, prove for n = ...
0
votes
1answer
41 views

Proof by induction with two variables

Giving proof by induction is normally very straight forward: $n+1$ and such. But how do you deal with two variables $m$ and $n$? Given this problem, how do I ensure that I'm proving for $n+1$ and ...
0
votes
1answer
58 views

Induction proof divisible by 5

Prove that for all n ∈ N, prove that $ 3^{3n+1} + 2^{n+1} $ is divisible by 5. So far what I've gotten is: Step 1: We will prove this by using induction on n. Assume the claim is true when n = k. ...
0
votes
0answers
65 views

Favourite proofs by induction?

I am searching for nice proofs by induction, that can be used to teach. I remember this example, that my analysis professor presented to us in first semester and I am searching for more such easily ...
2
votes
1answer
64 views

Proof by induction regarding maximum number of questions one can ask.

sorry for the pretty ambiguous title. It's otherwise hard to describe this problem without stating it in full. There are $n$ points drawn on a whiteboard. Between every pair of points $X$ and $Y$ ...
-1
votes
1answer
64 views

Prove $2n+3 \le 2^n$ for all integers $n \ge 4$.

I have already started the problem but I am unsure on how to proceed. Prove $2n+3 \le 2^n$ for all integers $n \ge 4$. Base Case: Choose $n = 4$. $2n + 3 \le 2^n$ $2(4) + 3 \le 2^4$ $8 + 3 \le ...
1
vote
1answer
61 views

Proof modular equality by induction

I'm trying to prove using induction that $5^{2^{x-2}} \equiv 1 + 2^x \pmod{2^{x+1}}$ So far, I have: Base case: $x = 2, 5 \equiv 5 \pmod{8}$, It is true. $x = 3, 25 \equiv 9 \pmod{16}$, It is true. ...
1
vote
1answer
18 views

Question on induction and the application of an 'equivalent' induction hypothesis.

I am working on the following problem which I decided to solve by induction Problem: Let $(a_n), (b_n)$ be sequences for $n \geq 1$. Define $B_n:= \sum_{i=1}^n b_n$ for $n \in \mathbb{N}$. Show ...
0
votes
1answer
42 views

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 ...
1
vote
2answers
44 views

Proof by induction for $ 2^{k + 1} - 1 > 2k^2 + 2k + 1$ for $k > 4$

I was given this proof for hw. Prove that $ 2^{k + 1} - 1 > 2k^2 + 2k + 1$ So, far I've gotten this Basis: $k = 5$, $2^{5 + 1} - 1 > 2\cdot5^2 + 2\cdot5 + 1$ => $63 > 61$ (So, the basis ...