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

2
votes
1answer
110 views

Proof of Euler's Totient Theorem

I have seen quite a few proofs of Euler's Totient Theorem that $a^{\phi(n)}≡1 \pmod n$ for all $a$ relatively prime to $n$. However, none have been done using induction. That is what I have been ...
0
votes
3answers
133 views

Proving that the square root of 5 is irrational

Prove that $\sqrt{5}$ is irrational. I begin with the identity $(\sqrt{5} + 2 )(\sqrt{5} - 2 ) = 1$. Then I am told to extract $\sqrt{5}$ from the first or second factor and consider it to be ...
3
votes
3answers
262 views

Proof of 3-chain subsequence problem from assignment 2 of MIT OCW 6.042

I was trying to solve this question but stuck with how do I prove it so. I do have the intuition but how to prove it? Here is the link to the page and this one is the problem 1!! ...
0
votes
0answers
52 views

Prove if $a_{1},…,a_{n}$ are elements of a group $G$, then $(a_{1}*a_{2}*…*a{_n})^{-1}=((a_{1})^{-1})*…*((a_{n})^{-1})$

Using induction Base case: $n=1$ then $(a_{1})^{-1} = (a_{1})^{-1}$ which is correct. Assume this is true for some k∈Z. Then for the $k+1$ case $(a_{1}*a_{2}*...*a_{k} ...
0
votes
3answers
73 views

proof by mathematical induction with the summation operator? [duplicate]

$$ \sum_{k=1}^n k^3 = \left( \sum_{k=1}^n k \right)^2 $$ I can't quite understand this expression, and in fact this is my biggest difficulty in finding a solution. Can someone please explain to me ? ...
2
votes
1answer
450 views

Using Induction to prove complete binary trees

Prove a complete binary tree has an odd number of vertices. My attempt at the solution: Basis step: A binary tree with a height of 0 is a single vertex. This would result in the tree having an odd ...
1
vote
1answer
45 views

How do I prove by mathematical induction that $n!<n^{n-1}$ where $n\geq3$? Did I do it right?

Suppose $n$ is equal or bigger than $3$. It's obviously true for $n=3$ that $n!<n^{n-1}$. To show more generally that $$k! < k^{k-1} \text{ for some } k,$$ is it as simple as saying $$(k+1)! ...
3
votes
5answers
86 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: ...
2
votes
1answer
50 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 ...
2
votes
2answers
74 views

On problems which can be proved easier if we use a different induction step.

Say we have a property $P$ defined on the natural nubers. Usually students are taught that to pove $P(n)$ is true for all $n\in\mathbb N$ you have to do the following: make a basis and use ...
2
votes
1answer
40 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 ...
4
votes
3answers
276 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
84 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
1answer
35 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 ...
0
votes
1answer
51 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 ...
2
votes
3answers
92 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 ...
1
vote
1answer
41 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 ...
5
votes
2answers
529 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
16 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
122 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 ...
4
votes
4answers
76 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 ...
2
votes
2answers
47 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 ...
-1
votes
1answer
57 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}$$
0
votes
0answers
36 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 = ...
1
vote
3answers
135 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 ...
1
vote
1answer
84 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 ...
1
vote
1answer
29 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 ...
0
votes
1answer
26 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 ...
1
vote
4answers
87 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
1answer
66 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 ...
-2
votes
2answers
78 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}.$
4
votes
3answers
217 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 ...
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 ...
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 ...
1
vote
3answers
128 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 ...
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
354 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
205 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
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
74 views

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