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
1answer
22 views

Difference between Inductive hypothesis and inductive goal

For example: $\forall x: \forall y: \forall z:$ x * (y + z) = (x * y) + (x * z) by induction on z, letting x and y be arbitrary. What would be my inductive hypothesis and inductive goal in this ...
-2
votes
2answers
100 views

Prove $\sum^n_{i=1} (2i-1)=n^2$ by induction [closed]

The problem is to prove that $$\sum^n_{i=1} (2i-1)=n^2$$ for all $n \geq 1$ by induction.
1
vote
2answers
28 views

Proof by induction confused about inductive step

I have these notes, but I'm confused on what is happening at the inductive step. Theorem: $\forall n \in \mathbb{N} 3 | (n^3-n) $ Inductive Step: For $n \geq 0, show P(n) \Rightarrow P(n+1) is ...
1
vote
2answers
43 views

Prove using induction that $2^n < \binom{2n}{n} < 4^n$ for $n \geq 2$

Trying to prove that, for $n\geq2$, $2^n < \binom{2n}{n} < 4^n$. Inductive hypothesis: Assume $P(k)$ is true: \begin{align} 2^k < \binom{2k}{k} < 4^n \\\\ \end{align} Show $P(k+1)$ \...
0
votes
3answers
61 views

Proof by induction using factorials

Prove by induction that: There are exactly $n-k+1\choose{k}$ choices for choosing k numbers from the set {1,,,,n} with no two numbers adjacent. I have no idea :( I thought I would start with base ...
0
votes
2answers
24 views

Clarify worked example on induction with inequality

I'm reading through example #3 on Purplemath. I don't understand the reasoning behind the line I marked $\dagger$ and why the underlined term, $\underline{2^k}$ gets added!? I'm rewriting the example: ...
1
vote
5answers
99 views

Mathematical Induction Divisibility Problem

Prove that if $n \ge 1$ is a positive integer, then $13^n − 6^n$ is divisible by $7$. In proving the $n = k+1$ case, I get to $133k + 6^k\cdot13 - 6\cdot13^k = 7M$, where $M$ is a positive integer. $...
0
votes
1answer
22 views

Base case not the same for two equivalent forms of the statement

Prove that the following statement holds for all natural numbers: $$1\cdot2\cdot2^{n} + 2\cdot3\cdot2^{n-1} + \dots +n\cdot(n+1)\cdot2+(n+1)\cdot(n+2) = 2^{n+4}-(n^2-7n+14)$$ I don't need help with ...
-1
votes
1answer
56 views

Proof by induction: $2(\sqrt n - 1) < \sum\limits_{i=1}^n \left(\frac{1}{\sqrt{i}}\right)$ [duplicate]

Need help with proof by induction for: $$2(\sqrt n - 1) < \sum_{i=1}^n \left(\frac{1}{\sqrt i}\right)$$ For n=1: Good. Assuming for n, trying to proof for (n+1)... Thanks.
3
votes
3answers
138 views

Proving that the sum of fractions has an odd numerator and even denominator.

I'm struggling to show that, for all $n>1$ $$ 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} = \frac{k}{m} $$ where $k$ is an odd number and $m$ is an even number. Proof: The proof is by ...
-2
votes
1answer
53 views

Induction proof dealing with geometric series [duplicate]

$1+r+(r^2)+...+r^n= \frac{1-r^{n+1}} {1-r}$ Any help would be appreciated in solving the geometric series.
-1
votes
4answers
46 views

Prove $\sum\limits_{i=1}^n \frac{1}{i(i+1)} = \frac{n}{n+1}$ by induction [closed]

Using induction, prove that $$\sum\limits_{i=1}^n \frac{1}{i(i+1)} = \frac{n}{n+1}$$ Any help would be appreciated.
0
votes
0answers
22 views

Commutative proof by induction

The distributive law for naturals is: $\forall x: \forall y: \forall z:$ x * (y + z) = (x * y) + (x * z) Suppose we set out to prove this by induction on z, letting x and y be arbitrary. What is our ...
1
vote
1answer
83 views

Interpretation of 2 proofs involving limits at infinity and mathematical induction

I have 2 exercises that I think are related to each other. I think they should be proved by mathematical induction. They are: prove that: limit of n which approaches infinity $(2^n / n!) = 0$ prove ...
1
vote
4answers
56 views

Prove by induction: $2!\cdot 4!\cdot 6!\cdot\cdot\cdot (2n)!\ge ((n+1)!)^n$

Prove by induction: $2!\cdot 4!\cdot 6!\cdot\cdot\cdot (2n)!\ge ((n+1)!)^n$ For $n=1$ inequality holds. $(*)$For $n=k$ $2!\cdot\cdot\cdot (2k)!\ge ((k+1)!)^k$ Multiplying LHS and RHS with $(2k+2)!$...
0
votes
1answer
53 views

Prove by Induction that Norms in a Finite Dimensional Space are Equivalent?

I would have thought that this is a good candidate for an inductive proof, but I have searched for one and failed. Is there such a proof, and if not why not ? Here's how far I got. It's easy to ...
0
votes
2answers
69 views

Induction proof using mean value theorem

Let $\alpha\in(0,1)$. Use the mean-value theorem to show that ln$(1-\alpha^k)>-\alpha^k/(1-\alpha)$ for all $k\in \mathbb{N}$. So I know that the mean value theorem is $\frac{f(b)-f(a)}{b-a}=f'(c)$...
1
vote
1answer
171 views

Differentiation- proof by Induction

Here is my problem: "Suppose f is a differentiable function whose domain is $(-\infty,\infty)$. We define an infinite sequence of functions $f_n(x)$ as follows: $f_1(x)=f(x), f_2(x)=f(f_1(x))$, ...
0
votes
2answers
65 views

Induction Proof $n! < n^n$

How would you go about proving $n! < n^n$ using a mathematical induction proof? I understand how to solve inductive proofs with = but I'm getting a bit lost in this example. Any help is much ...
0
votes
2answers
47 views

Prove by induction: $\frac{2^{2n}}{n+1}<\frac{(2n)!}{(n!)^2},n>1$

Prove by induction: $\frac{2^{2n}}{n+1}<\frac{(2n)!}{(n!)^2},n>1$ For $n=2$ equality holds. For $n=k$ $$\frac{2^{2k}}{k+1}<\frac{(2k)!}{(k!)^2}$$ For $n=k+1$ $$\frac{2^{2k+2}}{k+2}<\...
-6
votes
3answers
66 views

Proof by induction help!!! [closed]

Prove by induction that for all natural numbers $n\geq 2$ , $2^n+n^2<3^n$
0
votes
0answers
17 views

Prove by induction that if k $\in$ $\mathbb{N}$ and $g(x)= \sum^{\infty}_{n=0} b_{n} x^{n}$ converges absolutely

The book I am using for my Advance Calculus course is Introduction to Analysis by Arthur Mattuck. Prove by induction that if k $\in$ $\mathbb{N}$ and $g(x)= \sum^{\infty}_{n=0} b_{n} x^{n}$ converges ...
-1
votes
1answer
61 views

Proof by induction (Involving sets and factorials)

For all $k$, $n\in{\Bbb{N_0}}$ such that $k ≤ n$ we define: $\binom{n}{k}:=\frac{n!}{k!(n-k)!}\in{\Bbb{Q}}$ I am trying to do a proof by induction for this question. (a) Show that $\binom{n}{k} = \...
1
vote
2answers
48 views

Interpretation of a statement that I think I can prove by mathematical induction

I want to prove by mathematical induction the following statement: for any sequence (a_k) of non negative real numbers holds that: $$(1+a1)(1+a2)...(1+a_n) >= 1 + a_1 + a_2 + ... a_n$$ I think ...
4
votes
4answers
758 views

Write on my own my first mathematical induction proof

I am trying to understand how to write mathematical induction proofs. This is my first attempt. Prove that the sum of cubic positive integers is equal to the formula $$\frac{n^2 (n+1)^2}{4}.$$ I ...
-1
votes
1answer
40 views

Prove that a group is dense in an interval

I tried many ways to solve it and I think it is supposed to be solved using induction, but I seem to get stuck at the very beginning of the induction. I'd like to hear your suggestions of ways to ...
4
votes
3answers
373 views

How to write mathematical induction?

Reading the literature about mathematical induction, I have learnt that there are between 4 and 3 steps in reasoning and writing the proof. I say between 3 and 4 because actually I see that texts and ...
10
votes
2answers
316 views

Proving that $\sum_{a=1}^{b} \frac{a \cdot a! \cdot \binom{b}{a}}{b^a} = b$

Prove that for all positive integers $b$ that $$\sum_{a=1}^{b} \frac{a \cdot a! \cdot \binom{b}{a}}{b^a} = b.$$ My idea is induction, but I cannot figure stuff out on the inductive step.
2
votes
2answers
66 views

Proof of a sum with binomial coefficients $\sum_{k=1}^n (-1)^{k+1}{\binom nk}\frac{1}{k} = 1 + \frac{1}{2} + \ldots +\frac{1}{n}$ [duplicate]

I need to prove: $$\sum_{k=1}^n (-1)^{k+1}{n \choose k}\frac{1}{k} = 1 + \frac{1}{2} + \ldots +\frac{1}{n}$$ for $n \in \mathbb N$ I should use mathematical induction. So, I've tried going simply ...
2
votes
2answers
58 views

Prove by induction: $\left(\frac{1}{n+1}+\frac{1}{n+2}+…\frac{1}{2n}\right)^2<\frac{1}{2},n\ge 1$

Prove by induction: $\left(\frac{1}{n+1}+\frac{1}{n+2}+...\frac{1}{2n}\right)^2<\frac{1}{2},n\ge 1$ For $n=1$ inequality holds. For $n=k$ $$\left(\frac{1}{k+1}+\frac{1}{k+2}+...\frac{1}{2k}\...
0
votes
1answer
30 views

How proof this with induction.

I'm trying to address this exercise but do not know how to approach it: if $f(n) = G(n)-G(n-1)$ for all $n \geq 1$, prove that $f(1) + f(2) + f(3) + \cdots + f(n) = G(n)-G(0)$ for all $n \geq 1$. ...
2
votes
1answer
106 views

Learning how to prove by mathematical induction for the first time [duplicate]

So, I have to prove this by mathematical induction and I have never done it! $$\sum_{i=1}^n i^2 = n(n+1)(2n+1)/6$$ However, I have learnt better the theory behind this way to prove statements and ...
1
vote
2answers
31 views

Proof by Induction for n!$\gt$n2$^n$

For all natural number n with n$\ge$6. Prove by induction that n!$\gt$n2$^n$. I proved the base step by showing that n$=$6 and that 720 $\gt$ 384. Then I assumed that n$=$k. Then for the third step I ...
1
vote
2answers
58 views

Can't prove $2^n > n$ with Mathematical Induction

As the title states, I have a problem with proving $2^n > n$ I can do the basis step fine: Basis step: "n = 1" 2^1 = 2 2 > 1 So it is true for $n$. But ...
0
votes
1answer
31 views

Proving $(1-\frac{1}{2})(1-\frac{1}{4})\dotsm(1-\frac{1}{2^n}) \geq \frac{1}{4}+\frac{1}{2^{n+1}}$ using induction

Prove using induction: $(1-\frac{1}{2})(1-\frac{1}{4})\dotsm(1-\frac{1}{2^n}) \geq \frac{1}{4}+\frac{1}{2^{n+1}}$. I know how to prove such equalities but not really inequalities. I tried ...
1
vote
1answer
20 views

How to inductively define a set?

I am trying to define a set inductively. Suppose the set I want to define is: S = {(a, b) | a, b ∈ Z,(a − b) mod 3 = 0}. I know that to define this inductively I need a basis, some rule to make a ...
0
votes
1answer
32 views

Showing S is a subset of A by structural induction.

I have a problem similar to: Let S defined recursively by (1) 5 ∈ S and (2) if s ∈ S and t ∈ S, then st ∈ S. Let A = {5^i| i ∈ Z+}. prove that S ⊆ A by structural induction. I've only done ...
3
votes
3answers
394 views

How do I derive a formula for this ∏ notation?

For $n\in\Bbb N$ and $n\ge 2$, find and prove a formula for $\prod_{i=2}^n\left(1-\frac1{i^2}\right)$. I can easily prove the formula using induction once I have the equivalent result but I'm having ...
1
vote
1answer
33 views

Proving A is a subset of S by mathematical induction?

Suppose I have a question similar to: Let $S$ be defined recursively by (1) $5 ∈ S$ and (2) if $s ∈ S$ and $t ∈ S$, then $st ∈ S$. Let $A = \{5^i \mid i ∈ Z+\}$. Prove that $A ⊆ S$ by ...
1
vote
1answer
79 views

Prove for any number n, it is possible to select $X = 2^n$ numbers from $2^{n+1}$ numbers s.t. the sum of X is divisible by $2^n$

Prove, for any natural number $n$, that it is possible to select $2^n$ numbers from any collection of $2^{n+1}$ natural numbers such that that sum of the $2^n$ numbers is divisible by $2^n$. I am not ...
0
votes
0answers
73 views

Prove the number comparisons it takes to find the min and max of a list by the split and conquer method

Prove that the number of comparisons it takes to find the min AND max of a list by the split and conquer method (split a list in half until there are multiple subsets of just 2 elements and compare ...
5
votes
2answers
73 views

Prove: $1+{n\choose 1}\cos\phi+{n\choose 2}\cos2\phi+…+{n\choose n}\cos n\phi=2^n\cos^n\frac{\phi}{2}\cos\frac{n\phi}{2}$

Prove: $\displaystyle 1+{n\choose 1}\cos\phi+{n\choose 2}\cos2\phi+...+{n\choose n}\cos n\phi=2^n\cos^n\frac{\phi}{2}\cos\frac{n\phi}{2}$ I used induction: For $n=1$ equality holds. For $n=k\colon$...
-1
votes
5answers
95 views

Proof: $\sqrt[n]{n} > \sqrt[n+1]{n+1}$ [duplicate]

How can I prove that $\sqrt[n]{n} > \sqrt[n+1]{n+1}$ for $n \in \mathbb{N} \setminus \{ 1,2 \}$ ? My approach: Step 1: $n_0 := 3 \qquad \sqrt[3]{3} > \sqrt[4]{4}$ which is true. Step 2: $\...
-1
votes
2answers
41 views

Prove by induction that $\sqrt[n+1]{n+1}<\sqrt[n]{n}$ for $n\ge 3$ [duplicate]

I've been dealing with this problem for almost 2 hours now, with hardly any progress. I'm to prove the following inequality using induction $$\sqrt[n+1]{n+1}<\sqrt[n]{n}$$ where $n≥3$, $n∈\mathbb{...
2
votes
5answers
524 views

Prove that sum $(\sqrt2+1)^n+(\sqrt2-1)^n$ is rational for even numbers

Let $n \in N$ Prove that $(\sqrt2+1)^n+(\sqrt2-1)^n$ is rational iff $n$ is even I have tried to do it in induction but got stuck... Any ideas for how to solve this? Thanks
2
votes
2answers
39 views

Show that $n^{n-3} \ge n!$ for n=9, 10,…

Show that $n^{n-3} \ge n!$ for n=9, 10,... I have tried to n=9 $9^{9-3} = 9^6 = 531411$ $9! = 362880$ So $9^6 \ge 9!$ is true My question is how do I prove it by every for n=9, 10,... by ...
0
votes
4answers
82 views

Mathematical Induction for $4 + 10 + 16 +…+ (6n−2) = n(3n +1)$

Use mathematical induction to prove: $$4 + 10 + 16 +…+ (6n−2) = n(3n +1)$$ I'm having a hard time understanding the induction process. Can someone please explain this to me?
1
vote
2answers
27 views

Show that, for all $n > 0$, $A^n = {a^n\over a − b} (A − bI) + {b^n\over b − a} (A − aI)$.

Let $A ∈ M_{2×2}(\mathbb{C})$ be a matrix having distinct eigenvalues $a \neq b$. Show that, for all $n > 0$, $A^n = {a^n\over a − b} (A − bI) + {b^n\over b − a} (A − aI)$. I'm trying to prove ...
2
votes
1answer
46 views

Let $A ∈ M_{2×2}(\mathbb{C})$ be a matrix having a unique eigenvalue $c$. Show that $A^n = c^{n−1}[nA − (n − 1)cI ]$ for all $n > 0$.

Let $A ∈ M_{2×2}(\mathbb{C})$ be a matrix having a unique eigenvalue $c$. Show that $A^n = c^{n−1}[nA − (n − 1)cI ]$ for all $n > 0$. I'm doing induction for this, the base step when $n=1$ gives ...
1
vote
1answer
50 views

Multiplying products of $p_1,p_2,\ldots,p_n$ gives a square.

Given $n+1$ ($n\ge 4$) arbitrary products of primes $p_1,p_2,\ldots, p_n$, prove multiplying some of the products gives a square. E.g., for $n=4$: $\{p_1,p_2,p_3,p_4,p_1p_3\}$ satisfies the ...