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

0
votes
2answers
32 views

Prove divisibility

We have the following proposition: $$P(n): 13^n+7^n-2\vdots 6$$. Prove $P(n)$ in two ways. I know that one of them is mathematical induction. I don't know many things about the other one, I know ...
0
votes
2answers
48 views

Proof by Induction - Math

Prove that for every integer n>=2: We have the summation of $$ \frac{1}{i(i-1)}=1-\frac{1}{n} $$ I tried the algebra with this proof, but couldn't get it. I know that you split the i-1 and the i ...
0
votes
1answer
19 views

Proof by Induction Question - as part of Russo Dye Theorem

I began with $x_{n+1} = \displaystyle \frac{x+x_n}{2}$ and did the first few iterations to find that it follows this pattern: $\displaystyle \frac{(2^n-1)x+x_0}{2^n}$. How can i show this is true for ...
0
votes
1answer
27 views

Prove by induction for$ P(x)$

$P(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0$,with $a_n\neq 0$. Using induction on $n$, prove that $P^{(n)}(x) = n!a_n$. So I start with $n=1$ but $P(x) =a_1x$ and $P^{(1)}(x)=1a_1$ are not equal because ...
0
votes
1answer
52 views

Mathematical Induction Proof 1 [duplicate]

Prove that for every integer $ n \geq 1$, we have $\displaystyle \sum_{j=1}^n j^3 = \left(\dfrac{n(n+1)}{2}\right)^2$ I know how to prove an induction proof, but I just can't get the algebra down on ...
1
vote
2answers
50 views

Proof By Induction Fibonacci Numbers

How do I prove that $$ f_{ 2n+1 } = 3f_{ 2n } + 1 - f_{ 2n-3 } $$ I'm not sure how to prove it using the defining recurrence of Fibonacci numbers.
1
vote
5answers
56 views

Prove that $2^n\geq2n-1$

Let $n\geq2$ with $n\in\Bbb N$. Prove that $$2^n\geq2n-1$$ I need to prove this using mathematical induction. This is what I've tried: $P(2): 2^2\geq2n-1 \\ P(k)\Rightarrow P(k+1) \\ P(k+1): ...
3
votes
1answer
54 views

Prove that any amount of money of at least 14c can be made up using 3c and 8c coins

I am reading a book on Discrete Mathematics, and I am on the chapter of mathematical induction. The first problem is the fairly common example of 1+2+...+n = n(n+1)/2, which I didn't have trouble ...
0
votes
1answer
41 views

a_1,a_2,a_3…..a_n of natural numbers different then 0.

I understoof the logic behind it but have no idea how to put it into words. ex: n=3 ther are 4 n sum series: 1,1,1 1,2 2,1 3 of natural numbers different then 0, will be called n sum series if the ...
0
votes
0answers
19 views

How to prove by induction/stromg induction [duplicate]

i have a question that i need to prove by induction or strong induction and I really dont know how to approach it let there be n a natural number. and a serial of numbers a1, a2,....ak of natural ...
0
votes
2answers
66 views

Weak Mathematical Induction for Modulo Arithmetic

Using Weak Mathematical Induction, I have to show that, for all integers $n \geq 1$, $8|3^{2n} -1$ I really don't know how to go about solving this problem. Currently I only have the base case and ...
1
vote
2answers
885 views

Prove by induction the predicate (All n, n >= 1, any tree with n vertices has (n-1) edges).

I'm stuck on this problem, posting my progress so far below. I've looked at similar questions here and here, but neither seem to directly prove the predicate by induction, with a base case followed by ...
0
votes
4answers
74 views

How to show $a_n = \frac{n+1}{n-1}$ is strictly decreasing by induction?

I can show this fact otherwise, but I can't seem to figure out the simple algebra to prove it by induction...Could someone provide a hint? I just need a push in the right direction. It seems too ...
2
votes
2answers
99 views

Mathematical Induction Proof - Exponent with n in denominator

Use mathematical induction to prove the following: $$\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+...+\frac{n}{2^n}=2-\frac{n+2}{2^n}; n ∈ N $$ I am having trouble figuring out how to solve this with an ...
1
vote
1answer
36 views

Another quick induction question for a recursively defined sequence (with closed form formula given)

I was given: A sequence is defined recursively by $a_0 = 1$, $a_1 = 4$, and for $n\ge2$, $a_n = 5a_{n-1} - 6a_{n-2}$. Use induction to prove that the closed form formula for $a_n$ is $a_n = ...
0
votes
2answers
48 views

mathematical induction, prove the expression with summation

how to prove by mathematical induction the below expression: can someone help me by proving it by the standart way
1
vote
1answer
42 views

Proof by induction that x_n < 2^n

Define $x_1=x_2=x_3=1$ and $$x_{n+1}=x_n+x_{n-1}+x_{n-2}$$ for $n≥3$. Prove that $$x_n<2^n \qquad ∀n\in\mathbb N$$ I have shown the base case and supposed the result in the inductive case. Then, ...
1
vote
4answers
51 views

Alternative proof for $\forall n\in\mathbb N (n\ge 6 \Rightarrow \exists a,b\in\mathbb N : n=3a+4b)$

Can I use only strong induction in order to prove $$\forall n\in\mathbb N (n\ge 6 \Rightarrow \exists a,b\in\mathbb N : n=3a+4b)$$ Is there any other option?
0
votes
1answer
38 views

Prove inequality holds

Show that: $\displaystyle 2! \cdot 4! \cdot... \cdot(2n)!>[(n+1)!]^n $ for $n>1$ where $n$ is natural I tried by induction but I stuck when I have to show that: $(2n+2)!>(n+2)!(n+2)^n$
0
votes
1answer
74 views

Prove by induction on a sequence

We have $$ n \in R $$ And an arithmetic sequence of natural numbers different than 0 that the sum of all its members = n $$ a_1,a_2,...,a_k $$ $$ a_1+a_2+...+a_k = n $$ I need to prove by ...
0
votes
1answer
46 views

Show that any connected graph $G$ satisfies $\lvert E(G)\rvert \geq \lvert V(G)\rvert -1 $

Show that any connected graph $G$ satisfies $\lvert E(G)\rvert \geq \lvert V(G)\rvert -1 $ by induction on the number of edges. My attempt: Base Case: For any connected graph $G$ let number of ...
1
vote
3answers
63 views

Mathematical Induction divisibility

So I'm trying to use mathematical induction to show that for all integers $n \ge 1$ , $$ 8|(3^{2n} - 1)$$ (is divisible by 8) I have my base case: [P(1)], $3^2 - 1 = 9 - 1 = 8$, since $8|8$, the ...
0
votes
0answers
35 views

Doob's decomposition Thm_ Got stuck applying induction in proving $Z_{n+1}$ is $F_n$ measurable?

Already know $Z_0=0$, and $$Z_{n+1}=E(X_{n+1}|F_n)-X_n+Z_n$$ $X_n$ is $F_n$ measurable, $F_n$ is a filtration. How to prove $Z_{n+1}$ is $F_n$ measurable? I tried to prove by induction. Since $Z_1$ ...
0
votes
1answer
67 views

General form of iterates $f^{n}(x)$ for $f(x) = \frac{x}{1-x}$

Let $f: \mathbb R\to\mathbb R$, $f(x) = \frac{x}{1-x}$. Define $f^{2}(x) = f(f(x))$, $f^{3}(x) = f(f(f(x)))$, ... Guess the form for $f^{n}(x)$ and prove your answer is correct using ...
1
vote
1answer
40 views

Help with Mathematical Induction [duplicate]

$$1^3+2^3+\cdots+n^3=\left[\frac{n(n+1)}2\right]^2$$ so far I have.. $$1^3+2^3+\cdots+k^3+(k+1)^3=\left[\frac{(k+1)(k+2)}2\right]^2$$ then.. ...
4
votes
0answers
69 views

Prove $\forall n\in\mathbb{N}, \exists m\in\mathbb{N}; n=\pm1^2\pm2^2\pm\cdots\pm m^2.$

And we choose the positive and negative signs in a way that the equation becomes true. I think it can be proved with mathematical induction. So here's how I begin: For $n=1$, $1=+1^2$ which is true. ...
7
votes
1answer
83 views

Is there a proof of $\sum_{n=0}^x {{(-1)^n(x-n+1)^x}\over{n!(x-n)!}} = 1$ using induction?

Can someone prove (or disprove) this equality? $$\sum_{n=0}^x {{(-1)^n(x-n+1)^x}\over{n!(x-n)!}} = 1$$ where the value of $x$ can vary. This is a pattern found in derivatives and stuff but I'm not ...
1
vote
1answer
55 views

The number $2^{3^n}+1$ is divisible by $3^{n+1}$ and not divisible by $3^{n+2}$.

Prove that for every $n\in \mathbb N$, $2^{3^n}+1$ is divisible by $3^{n+1}$ and not divisible by $3^{n+2}$. I was able to prove that $2^{3^n}+1$ is divisible by $3^{n+1}$ using induction. First, ...
0
votes
3answers
71 views

How to prove $ 1^3+2^3+… +n^3 = (1 + 2+ \dots +n)^2 $ by induction? [duplicate]

I need to prove that for each natural n: $$ 1^3+2^3+... +n^3 = (1 + 2+ ...+n)^2 $$ How do I do that? how do I know whether I should choose strong induction or simple induction?
1
vote
1answer
38 views

Show that $-2, -1, 0, i$ lies in the Mandelbrot set but that $1$ lies outside of it

The Question Let $c$ be a complex number. The complex numbers $z_n(c)$ are defined recursively by $z_1(c)=c$, $z_{n++1}(c)=(z_n(c))^2+c$ for $n\geq1$ The Mandelbrot set is defined by ...
1
vote
1answer
64 views

Finding the fake coin from $3^n$ coins by weighing (proving by induction)

I have a problem that I need to prove by induction and I don't know how.. I have $3^n$ gold coins. All of them weigh the same except one which is lighter than each of the others. Prove that the fake ...
2
votes
1answer
112 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 ...
3
votes
5answers
112 views

proving that $(n-1)^n>n^{n-1}$ [duplicate]

I want to prove that $(n-1)^n>n^{n-1}$, for $n>4$, $n$ is an integer. So I divided by $n^n$ and got: $(1-\frac{1}{n})^{n}>\frac{1}{n}$ I know that ...
0
votes
3answers
74 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 ? ...
3
votes
3answers
286 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!! ...
1
vote
0answers
54 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} ...
2
votes
1answer
476 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)! ...
2
votes
1answer
51 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
87 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: ...
27
votes
14answers
794 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
291 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
73 views

Proof by induction that the sum of the first $2n$ odd positive integers is $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 ...
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 ...
-1
votes
1answer
33 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
537 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
131 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
3answers
93 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 ...