Induction in general is the inference from the particular to the general. Mathematical induction is not true induction, but 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 ...

learn more… | top users | synonyms

0
votes
2answers
59 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 ...
0
votes
4answers
30 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
41 views

Proof of series with induction

I have the sum ...
0
votes
1answer
25 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
17 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
0answers
36 views

Prove that the truth value of $x_1 \lor x_2 \lor \ldots \lor x_n$ does not depend on how the formula is parenthesized

So the question is: Generalized Associativity of $\lor$. Prove that, for all positive integers $n$, all ways of parenthesizing the following logical statement have the same truth value: $$x_1 \lor ...
0
votes
3answers
40 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
32 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
7answers
66 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
25 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
1
vote
1answer
59 views

Prove that $\sum_{i=1}^na_i\sum_{i=1}^na^{-1}_i\ge n^2$ and $\sum_{i=1}^na_i^2\ge\frac1n$ [closed]

For $a_i>0$, $i=1, \dots,n$ prove the inequalities $a)$ $$\sum_{i=1}^na_i\sum_{i=1}^na^{-1}_i\ge n^2$$ $b)$ $$\sum_{i=1}^na_i^2\ge\frac1n,\quad \text{if additionally}\sum^n_{i=1}a_i=1$$ ...
3
votes
4answers
82 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
25 views

Proof by induction with variable other than $n$

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
41 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
336 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
32 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
32 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 ...
0
votes
0answers
28 views

Discrete Structrue

I was stuck with the following problem. Two players A and B play a game where they take turns adding numbers from 1 through 10, and the first person who gets to the target of 100 wins. Assume A ...
2
votes
2answers
61 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
62 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
25 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
32 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
61 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
37 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
227 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
83 views

prove weak induction implies strong induction

There is a solution from a year ago that I don't quite follow which is why I post this along with my attempt, so it is not a duplicate. Prove weak induction implies strong induction: weak ind. ...
1
vote
0answers
28 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
70 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
2answers
34 views

Induction on the number of marbles in a heap.

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
38 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
34 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
24 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
44 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
45 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
5answers
54 views

Prove that $e^x \ge$ its Maclaurin polynomial with n terms [closed]

a) show that $e^x \geq 1+x$ for all $x\geq 0$ b) deduce that $e^x \geq 1+x+\frac{1}{2}x^2$ for $x\geq0$ c) use induction to prove that for $x\geq 0, n\in \mathbb{N}$ $$e^x\ge ...
2
votes
1answer
52 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
57 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
46 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
17 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
36 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
34 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 ...
0
votes
0answers
15 views

What is the growth of $T(n)=aT\left(\left\lfloor\sqrt[k]{n}\right\rfloor\right)+b\log(n)$

What is the growth of $T(n)=aT\left(\left\lfloor\sqrt[k]{n}\right\rfloor\right)+b\log(n)$ where $a$ and $b$ are positive reals and $k \ge 2$ is an integer? This is a generalization of my answer to ...
2
votes
2answers
61 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) = ...
2
votes
3answers
56 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
32 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
0answers
28 views

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

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
38 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
44 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 ...
0
votes
1answer
26 views

Proof: Probability using Induction

You have $n$ coins $C_1$, $C_2$, ..., $C_n$ for $n \in \mathbb{N}$. Each coin is weighted differently so that the probability that coin $C_i$ comes up heads is $\frac{1}{2i + 1}$. Prove by induction ...
2
votes
1answer
52 views

Gossip problem proof by induction

Question Suppose there are $n$ people in a group, each aware of a scandal no one else in the group knows about. These people communicate by telephone; when two people in the group talk, they ...