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

3
votes
1answer
159 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
57 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
17 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
448 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
54 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
46 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
56 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
438 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
43 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
44 views

Proof of series with induction

I have the sum ...
0
votes
1answer
69 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
39 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
45 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
36 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
239 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
46 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
4
votes
4answers
100 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
39 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
617 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 ...
1
vote
4answers
45 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
74 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 ...
1
vote
2answers
141 views

Inductive proof of the identity $\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$ [duplicate]

I'm trying to 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 prove it using induction (not a counting argument), I ...
2
votes
2answers
69 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
58 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
78 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
109 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
59 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
260 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
324 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
59 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
165 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
61 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
55 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
43 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
87 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
82 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
70 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
70 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$ ...
0
votes
1answer
65 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
69 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
19 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
45 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
53 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 ...
2
votes
2answers
100 views

Find recurrence relation of $T(n)=2T\left(\left\lfloor\sqrt{n}\right\rfloor\right)+\log(n)$

Sorry about the formatting of the title I'm not sure of the codes to make it look better. I need to find the recurrence relation of the following: $$T(0) = 1$$ $$T(n) = ...
3
votes
3answers
64 views

For every integer $n \geq 1$, prove that $3^n \geq n^2$.

It's been a while since I've done induction, and I feel like I'm missing something really simple. What I have is this: Base Case: $n=1$ $$3^n \geq n^2 \implies 3 \geq 1$$ Inductive ...
0
votes
1answer
40 views

Calc I limit/series question

Let $f : \mathbb R\rightarrow\mathbb R$ be a function that is differentiable at zero and such that $f(0)=0$. Show that for each $n\in \mathbb N$ we have that ...
1
vote
1answer
119 views

Harmonic numbers, proof that h2^k >= 1+(k/2) with induction [duplicate]

I'm just starting with the concept of proving mathematical statements with induction. The complete exercise with solution can be found under: ...
0
votes
1answer
46 views

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 = ...
1
vote
1answer
51 views

Strong Induction Proof / Algebra

Alright, I pretty much have the proof done, now just trying to do the algebra on it. This is the question... The information I have is: $$a_k = C_1 r^k + C_2 s^k$$ $$a_{k-1} = C_1 r^{k-1} + C_2 ...