# Tagged Questions

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

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 ...
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.
28 views

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 ...
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.
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 ...
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.
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.
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 ...
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 ...
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)!$...
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 ...
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)$...
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))$, ...
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 ...
47 views

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$. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$...
95 views

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