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

2
votes
1answer
33 views

The disease problem

Students are sitting in a n * n grid. There's a disease spreading among them in a particular fashion. At start, there a 'k' students infected(At random). After every time step(equal intervals), the ...
3
votes
5answers
83 views

Inequality proof by induction, what to do next in the step [duplicate]

I have to prove that for $n = 1, 2...$ it holds: $2\sqrt{n+1} - 2 < 1 + \frac{1}{\sqrt2} + \frac{1}{\sqrt3} + ... + \frac{1}{\sqrt{n}}$ Base: For $n = 1$ holds, because $2\sqrt{2}-2 < 1$ Step: ...
21
votes
8answers
383 views

Examples where it is easier to prove more than less

Especially (but not only) in the case of induction proofs, it happens that a stronger claim $B$ is easier to prove than the intended claim $A$ (e.g. since the induction hypothesis gives you more ...
4
votes
3answers
140 views

Prove using a strategy stealing argument that player 1 has a winning strategy in the chomp game

I have no idea what this question is asking or how to prove it mathematically. I realize based on the strategy stealing theory that if player two has a winning stratagy then player one can use the ...
0
votes
1answer
56 views

Proof by induction 4n^2

Prove by induction, explaining each step carefully, that the sum of the first $2n$ odd positive integers is equal to $4n^2$. Let P(n) be the statement $P(n)=\sum_{n=1}^{2n} 2n-1 = 4n^2$ The $P(1)$ ...
0
votes
1answer
32 views

Show this tree exists for n >= 3

I wonder if you guys can help me find an easier solution for this. Show that for every n >= 3 a tree exists with exactly n nodes and n - 1 leaves. My instructor had a solution that basically ...
-1
votes
1answer
30 views

Proving a certain set is inductive?

Let $m$ be a natural number in a field $F$ and let $$ S_m= \{k:k\in N ~~~and~~~ k\leq m \}\cup\{x:x\in F, m<x\} $$ Show that the set $S_m$ is inductive. Thanks in advance!
5
votes
2answers
440 views

What is wrong with this induction proof?

What is wrong with this "proof" by strong induction? "Theorem": For every non-negative integer $n, 5n = 0$. Basis Step: $5(0) = 0$ Inductive Step: Suppose that $5j = 0$ for all non-negative integers ...
0
votes
1answer
14 views

Induction Question Sequences

Suppose a1, a2, a3, . . . is a sequence defined as follows: $a_1 = 1, a_2 = 3, a_k = a_{k−2} + 2a_{k−1}$ for all integers k ≥ 3. Prove that an is odd for all integers n ≥ 1. So I've started with the ...
0
votes
4answers
88 views

$3$ and $5 $cent coins

Prove that any amount of more that $7$ cents can be represented by $3$ and $5$ cent coins. (Assume $3$ cent coins exist.) Let P(n) be true if we can find $n$ cents with $3$ and $5$ cent coins. My ...
3
votes
4answers
69 views

How to prove $n!\leq(\frac{n+1}{2})^n$ [duplicate]

Prove that for $n\in\mathbb{N}$ $$n!\leq(\frac{n+1}{2})^n$$. I'v solved base case for $n=1$ $$1\leq(\frac{1+1}{2})^1=1$$ The second step I've mada was that I assumed that $n!\leq(\frac{n+1}{2})^n$ And ...
1
vote
3answers
67 views

Proving $\sum^{n}_{k=1} \frac{1}{\sqrt{k}}>\sqrt{n}$ by induction

Prove that $$\sum^{n}_{k=1} \frac{1}{\sqrt{k}}>\sqrt{n}$$ for all $n\in \mathbb{N}$ where $n\geq2$. I've already proven the base case for $n=2$, but I don't know how to make the next step. Is the ...
0
votes
2answers
39 views

How do I prove this product by induction?

$$n \in \mathbb{N} $$ $$ \prod_{k=1}^{n-1}\left( 1 + \frac{1}{k}\right)^k = \frac{n^n}{n!}$$ How do I prove this by induction? I tried something like this: $$ \left( 1 + \frac{1}{1}\right)^1 ...
0
votes
1answer
37 views

How to prove that for any sequence $(a_{k})$ of non-negative real numbers,$(1+a_1)(1+a_2)\cdot…\cdot(1+a_n)\geq 1+a_1+a_2+…+a_n$? [closed]

Use math induction prove that for any sequence $(a_{k})$ of non-negative real numbers, $$(1+a_1)(1+a_2)\cdot...\cdot(1+a_n)\geq 1+a_1+a_2+...+a_n$$
2
votes
2answers
34 views

Fibonacci Number basis Induction

The Fibonacci numbers are defined as follows, $$F_1 = 0, F_2 = 1, F_n = F_{n−2} + F_{n−1}, ∀n ≥ 3$$ Prove using induction that one can express any positive integer as a sum of distinct Fibonacci ...
2
votes
1answer
38 views

2(n-1) induction

There are $n$ cities and every pair of cities is connected by exactly one direct one-way road. Now more one-way roads have been added between some cities so that between some pairs of cities there may ...
1
vote
1answer
40 views

How to prove that $\forall n\in \mathbb{N}$, $\sum ^{n}_{i=1}i^{3}=\frac {n^{2}(n+1)^{2}}{4}$? [duplicate]

Use mathematical induction to prove that $\forall n\in \mathbb{N}$, $$\sum ^{n}_{i=1}i^{3}=\dfrac {n^{2}(n+1)^{2}}{4}$$ $$\begin{align*} \sum_{k=1}^{n+1} k^3 &= \sum_{k=1}^{n} k^3 + (n+1)^2 ...
-1
votes
1answer
49 views

How to prove using math induction that $\forall n\in \mathbb{N}$, $\sum ^{n}_{i=1}i^{2}=\frac{1}{6}n\left( n+1\right) \left(2n +1\right)$? [duplicate]

Use mathematical induction to prove that $\forall n\in \mathbb{N}$, $$\sum ^{n}_{i=1}i^{2}=\dfrac {n\left( n+1\right) \left(2n +1\right) }{6}$$
5
votes
3answers
131 views

After removing any part the rest can be split evenly. Consequences?

Let $S$ be a finite collection of real numbers not necessarily distinct . If any element of $S$ is removed then the remaining real numbers can be divided into two collections with same size and same ...
0
votes
0answers
35 views

Inductive proof of the property $f(k+2)=f(k)+f(k+1)$ for the numbers given in terms of the golden ratio [duplicate]

Help prove through induction that $f(k+2)=f(k)+f(k+1)$ using the golden ratio $\frac1{\sqrt5}\phi^n-\frac1{\sqrt5}\left(\frac{1-\sqrt5}2\right)^n$ $F_{n+2}=F_n+F_{n+1}$, using golden ration $f_n = ...
0
votes
1answer
70 views

Induction in a first order system with ZF

Suppose I have some characterization of the natural numbers $N$ in a first-order system under ZF. To be precise, I have $N = \lbrace n: \forall w:( w\space is\space inductive) \rightarrow n \in w ...
0
votes
0answers
19 views

Proving that the function has the stated upper and lower bounds

Is there a way to solve this without using induction? I have thought of using Riemann sum but I could not obtain the the upper bound.
1
vote
1answer
42 views

Proving a Recurrence Relation by induction

I have the Recurrence Relation: $ T(n)=T(log(n))+O(\sqrt{n}) $, and I'm being asked to prove by induction an upper bound. I'm also allowed for ease of analysis to assume $n=2^m$ for some $m$. So here ...
0
votes
1answer
12 views

How to prove that at Complete Binary Tree (CBT) at height $h$ we have $2^h$ leaves

I try to prove it by induction, please tell me if I'm right... The induction assumption - For every CBT at height $h$ there is $2^h$ leaves. The base of the induction is right (I'm writing this proof ...
1
vote
3answers
64 views

Set of palindromes with induction

Let $A = \{a_1, a_2, ..., a_k\}$ be a finite alphabet. a. Define, using structural induction, set of all palindromes of A. b. Find the recurrent pattern which represents the number of all ...
0
votes
1answer
17 views

Proof of the number of the leaves in a full binary tree

I need to proof by induction that at full binary tree there are $\frac{n+1}{2}$ leafs if $|V|=n$. So, I won't write you the whole proof, just my idea, and I'd like to know if this OK... So we ...
1
vote
4answers
63 views

Help proving $9^n-8n-1$ is divisible by $8$ for all $n > 1$ by induction

I have been trying to prove that $9^n-8n-1$ is divisible by $8$ for all $n$ integers greater than 1. My progress: Let $n = 2$. This gives us the expression equal to $64$ which is a factor of 8. Now ...
0
votes
0answers
40 views

How to solve the following recurrence: $g(n) = g(\log{n}) + n^{1/2}$

It seems to me that the following recurrence: $g(n) = g(\log{n}) + n^{1/2}$ has a tight upper bound of: $O(n^{1/2})$, however I am not sure how to prove this. Specifically, I would like to find an ...
0
votes
0answers
35 views

prove well-ordering of nonnull subset of positive ints using weak induction

prove well-ordering of nonnull subset of positive ints using weak induction Let $S\subseteq Z^+$. If $S$ has one element it must be the smallest element and hence it is well-ordered. Assume true ...
-1
votes
2answers
38 views

Proof by induction that certain number is an integer

Prove that the number $\frac{2n^5}{5} + \frac{n^4}{2} - \frac{2n^3}{3} - \frac{7n}{30}$ is an integer $\forall n \in \mathbb{N}.$
0
votes
1answer
22 views

Questions about k elements subset of an n elements set.

I need to prove by induction that the number of 2-elements subset of an n elements set is $\frac{n(n-1)}{2}$ I am stuck on where I should start from and how should I solve this. I am guessing that ...
4
votes
3answers
98 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
28 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
40 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
21 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
41 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
99 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 ...
2
votes
1answer
25 views

Induction proof for a summation

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
40 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 ...
0
votes
1answer
34 views

Using induction to prove that $ \prod_{i=1}^{n} (1+a_{i}) \geq 1 + \sum_{i=1}^{n}a_{i} $ [closed]

I started a course in my university and I am having trouble with answering this question: Prove using Mathematical induction, for every real, non-negative 'n' number $$(a_{i}\geq 0)$$ the ...
0
votes
0answers
11 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
256 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
37 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
37 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
50 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$
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 ...