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

1
vote
1answer
44 views

Prove summations are equal

Prove that: $$\sum_{r=1}^{p^n} \frac{p^n}{gcd(p^n,r)} = \sum_{k=0}^{2n} (-1)^k p^{2n-k} = p^{2n} - p^ {2n-1} + p^{2n-2} - ... + p^{2n-2n}$$ I'm not exactly sure how to do this unless I can say: ...
0
votes
1answer
26 views

proof some inequality by induction

I got to proof the following in-equality by induction for an assignment but having a hard time. $$ \frac{2n}{(a+b)^n} \leq \frac{1}{a^n} + \frac{1}{b^n} $$ $a,b > 0$ Thanks in adavance!
2
votes
1answer
47 views

“Cascade induction”?

I refer to this answer. The answer is based on several simplification steps, all of them proven by induction. $$S_n = 2903^n - 803^n - 464^n + 261^n$$ $$T_n = 2642\cdot2903^n - 542\cdot803^n - ...
0
votes
1answer
23 views

Closed Form Summation Example

$$ \sum_{i=1}^n (ai +b) $$ Let $n \geq 1$ be an integer, and let $a,b > 0$ be positive real numbers. Find a closed form for the following expression. In other words you are to eliminate the ...
1
vote
1answer
24 views

Proof By Induction - $n^2 = \sum_{i=1} ^{n} (2i-1)$ for all $n\geq 1$

Using Proof By Induction I am trying to prove the following: $n^2 = \sum_{i=1} ^{n} (2i-1) $ for all $n\geq 1$ Here is my solutions so Far: Base Case: $n=1, LHS: 2(1)-1 = 1, RHS = 1^2 = 1, True$ ...
8
votes
4answers
166 views

Proving that $\frac{1}{n}+\frac{1}{n+1}+\cdots+\frac{1}{2n}>\frac{13}{24}$ by induction. Where am I going wrong?

I have to prove that $$\frac{1}{n}+\frac{1}{n+1}+\dots+\frac{1}{2n}>\frac{13}{24}$$ for every positive integer $n$. After I check the special cases $n=1,2$, I have to prove that the given ...
1
vote
0answers
17 views

Show that $f(b^i n) \le c^i f(n)$

Let $f$ be a b-smooth function. Let $c$ and $n_0$ be constants such that $f(b n) \le c f(n)$ $\forall $ $n \ge n_0$. Show that $\forall $ $ i \in \mathbb{N}, f(b^i n) \le c^i f(n)$ I thought I should ...
-4
votes
0answers
31 views

Prove, by induction that $a_{n} > \frac{1}{2^n}$ for all $n \in \mathbb{N}$ [on hold]

$$a_{1} = \frac{5}{2} $$ $$a_{n+1} = \frac{1}{2}(a_{n} +2)~\forall~n\in\mathbb{N} $$ Prove, by induction that, $$a_{n}\gt \frac{1}{2^n}~\forall~n\in\mathbb{N}$$
2
votes
3answers
35 views

$\sum_{k = 1}^{n} \frac{1}{k^{2}} < 2 - \frac{1}{n}$ [duplicate]

Prove that for $n\geq 2, \: \sum_{k = 1}^{n} \frac{1}{k^{2}} < 2 - \frac{1}{n} $ I used induction and I compared the LHS and the RHS but i'm getting an incorrect inequality
0
votes
1answer
25 views

Induction Mathematics and Factorials

\usepackage{amsmath} Evaluate the sum $\sum_{k=1}^{n} {k\over (k+1)!}$ $\sum_{k=1}^{1} {1\over (1+1)!} = {1\over 2}$ $\sum_{k=1}^{2} {2\over (2+1)!} = {5\over 6}$ $\sum_{k=1}^{3} {3\over (3+1)!} ...
0
votes
2answers
33 views

Proofing Induction Mathematics

I have just started to cover induction mathematics in my Discrete Mathematics class and I'm a little confused as to where to go with this problem. Am I on the right track? Prove that 9 divides (n^3 ...
4
votes
2answers
45 views

Proving that $F_{kn}$ is a multiple of $F_n$ by induction on $n$ (Fibonacci numbers)

Question: I want to prove that $F_{kn}$ is a multiple of $F_n$. Approach: I have to deduce this result from the following results: $$F_{n+k} = F_{k}F_{n+1} + F_{k-1}F_{n}$$ I have shown the ...
3
votes
2answers
35 views

Proving $1+5+9+\cdots+(4n+1) = (n+1)(2n+1)$ by induction (is there a typo?)

Using mathematical induction, prove that $$1+5+9+\cdots+(4n+1) = (n+1)(2n+1).$$ I understand the steps to take in order to prove by induction. It is also to my understanding that step 1 would be ...
4
votes
2answers
62 views

Proving that $3^n<n!$ when $n\geq 7$

It's been 10 years since my last math class so I'm very rusty. How would I go about proving $$3^n < n!$$ where $n \geq 7$? I understand that factorials grow faster than set values with a variable ...
2
votes
4answers
74 views

Rewrite $\sum_{i=0}^{n-1} (2i+1)=n^2$ to start induction from $k = 0$?

I'm trying to learn mathematical induction. The text asks for being totally rigorous i.e start induction from $k=0$. I want to prove that $$\sum_{i=0}^{n-1} (2i+1)=n^2,$$ i.e. the sum of the first ...
0
votes
2answers
50 views

Construction of Natural Numbers

I am trying to prove that the natural numbers can be constructed from the product of a power of $2$ and an odd number. For all $n \neq 0$ in the natural numbers, $n = (2k+1)(2^p)$, where $k$ and $p$ ...
-3
votes
0answers
25 views

Prime numbers proof [on hold]

Statement: Let n be a positive integer. There exists a prime number greater than n. Proof: Consider m = n! + 1. We know that m is divisible by some prime p. But no number between 2 and n is a ...
12
votes
4answers
193 views

Proving $\sqrt{1+\sqrt{2+\cdots+\sqrt{n}}} < 3$ for $n\geq 1$ by induction

How can I prove by induction that $\sqrt{1+\sqrt{2+\cdots+\sqrt{n}}} < 3$ for $n\geq 1$? My guess is that there must be another form to express the sum of nested square roots, but I don't know how ...
-4
votes
2answers
53 views

Proof By Induction [on hold]

I am trying to prove the Following, However, I dont understand what to do at the Inductive Step: Any Help would be appreciated!
-2
votes
0answers
20 views

mathematical induction 4th step [on hold]

Trying to get past the 4th step, where we need to prove it true for $n=k+1$. To simplify $\dfrac{5 (5^k - 1)}{4} + \dfrac{5 [5^{k + 1} - 1]}{4}$ to $5^{k + 1}$ . stuck with $\dfrac{3 (5^{k + 1}) - ...
4
votes
1answer
41 views

Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \le j \le n$

Let $p$ be a prime number and $a_1, a_2, \ldots, a_n$ be integers. Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \leq j \leq n$. The hint was to use induction. ...
0
votes
3answers
44 views

Find a formula for $ 1\times3^0 + 3\times3^1 + 5\times3^2 + … +(2n+1)\times3^n$.

The original exercise is to find a formula for this and prove it via induction. However, I am having a problem deriving such a formula. How do you normally approach this types of problems, is it a ...
0
votes
1answer
19 views

How to go about induction that deals with inequalitites

The only thing i've been able to do is to prove it for 1. How do i go about prvoing it for k+1?
0
votes
1answer
26 views

Nim Variant - Strong Induction Proof

Here we will play a variant of Nim where there is an additional move option in some cases. If two or more piles have the same number of stones, a player may remove the same number of stones from ...
0
votes
1answer
29 views

How to perform induction step in this question?

Q:Prove By induction $2^{n+1} > n^2$ for all positive integers. Step 1: Base case: $n=1$, we get $4>2$ Step 2: Induction hypothesis: $n=k, 2^{k+1} > k^2$ Step 3: Induction Step: to ...
-1
votes
1answer
105 views

Proving by induction on the number of vertices that: every acyclic simple graph is bipartite

Prove that every acyclic simple graph is bipartite, by the use of induction. I have quite some trouble with induction. Specifically, I know that acyclic graphs have at least one vertex that has a ...
3
votes
3answers
51 views

Why are two base cases needed to prove that $n<2^n$ for all $n\geq 0\,$?

So I understand more than one base case is needed when there is a recurrence relation like the Fibonacci sequence. But I don't understand why two base cases are needed in the below example. Is there ...
3
votes
4answers
75 views

How to prove $ \sum\limits_{k=1}^{n}\frac{k}{(k+1)!}=1-\frac{1}{(n+1)!}$ using induction?

This is as far as I get. I get stuck here because both sides to not equal each other, but I am not sure what I am doing wrong. $$ \sum\limits_{k=1}^{n}\frac{k}{(k+1)!}=1-\frac{1}{(n+1)!}$$ Assume: ...
1
vote
4answers
65 views

Solution verification: Prove by induction that $a_1 = \sqrt{2} , a_{n+1} = \sqrt{2 + a_n} $ is increasing and bounded by $2$

I have the following recursive relation (sequence): \begin{align} a_1 = \sqrt{2}, \quad a_{n+1} = \sqrt{2 + a_n} \end{align} My Try: I'm a little skeptical of my manipulations near the end but it ...
0
votes
1answer
28 views

Prove by induction $n^{1/n} ≤ \frac{n+1}{2}$

The problem Prove by induction: $n^{1/n} ≤ \frac{n+1}{2}$ Attempt at solution I started off with the usual steps for an MI problem. We start with the $P_1$ case: for $P_1$, LHS = 1 and RHS = 1 ...
0
votes
1answer
39 views

context-free languages operation closure

The following operation is defined on formal languages. $ operation1(L) = \lbrace w \ | \ wxy \in L, \ \forall x \forall y \ (|x|=|w|) \ \wedge (|y| = |w| ) \rbrace $ Prove that context-free ...
2
votes
1answer
34 views

Use Induction to Show $(1+a)^n \ge 1 + na$

If $a$ $\in$ $\mathbb R$ $\ni$ $a > -1$, then ($\forall n$ $\in$ $\mathbb R$) ($(1+a)^n \ge 1 + na$) My main concern is twofold: Firstly, I am concerned that constant $a$ in the proposition may ...
1
vote
4answers
63 views

Proving by induction that $n^2 - 7n - 2$ is divisible by $2$

Now proving by induction is fairly simple. However, this is a multiple choice problem whose answers don't make any sense to me. The actual problem goes as follows: To prove by induction that $n^2 - ...
1
vote
1answer
36 views

How can i prove using induction that the Hadamard matrices are orthogonal?

I can't figure out how to prove using induction that the dot product of 2 rows in a Hadamard matrix is 0. I've always thought of it as just a property of the type of matrix.
1
vote
1answer
42 views

Proof of Newton Girard formula symmetric polynomials

Newton Girard formula states that for $k>2$: \begin{equation} p_k=p_{k-1}e_1-p_{k-2}e_2+\cdots +(-1)^{k}p_1e_{k-1}+(-1)^{k+1}ke_{k} \end{equation} where $e_i$ are elementary symmetric functions and ...
0
votes
3answers
56 views

Proof By Induction $2^n \ge n^2$ for $n\ge4$

I am trying to prove the following, and here is what I have done: Can somebody help to complete this? $2^n \ge n^2$ for $n\ge 4$ $n=4$, LHS: $2^4 = 16$, RHS: $4^2=16$, $16=16$ Therefore TRUE Assume ...
0
votes
1answer
36 views

Proving $2n-8<n^2-8n+14$ for all $n\geq 7$ by induction

For what values of the natural number $n$ is $2n-8 < n^2-8n+14$? (must use induction) I have determined that $n$ appears to work for all values except $n=4,5,6$. I was wondering if this proof ...
1
vote
5answers
54 views

Mathematical Induction on a Subset of the Natural Numbers

I am given a strict inequality of the form $$ 2n - 8 < n^2-8n+14, $$ where $n$ belongs to the set of natural numbers $\mathbb{N}$ (in this case $n$ does not equal 0). I am asked, for what values ...
4
votes
4answers
94 views

Prove $\sum_{i=2}^{n}\frac{1}{(n-1)n}$ = $\frac{(n-1)}{n}$ using induction.

I need to prove $\sum_{i=2}^{n}\frac{1}{(i-1)i}$ = $\frac{(n-1)}{n}$ using induction. I am getting stuck midway through the inductive step. Here is what I have: $\forall n\geq 2$, where ...
1
vote
4answers
68 views

Prove that for all positive integers $n$, $2^1+2^2+2^3+…+2^n=2^{n+1}-2$ [duplicate]

I want to prove that for all positive integers $n$, $2^1+2^2+2^3+...+2^n=2^{n+1}-2$. By mathematical induction: 1) it holds for $n=1$, since $2^1=2^2-2=4-2=2$ 2) if $2+2^2+2^3+...+2^n=2^{n+1}-2$, ...
2
votes
2answers
34 views

Proof By Induction $n^2 > 3n$ where $n\ge 4$

I am trying to prove the following example, however I seem to be getting a little stuck: For $n\in\mathbb N$, $n\ge 4, n^2>3n$ What I have Done: Base Case:$ n=4$, LHS: $4^2 = 16$, RHS: $3\cdot 4 ...
0
votes
2answers
62 views

Explaining why proof by induction works [duplicate]

I am learning math proofs for the first time. So I cannot discern the reason for all the details in a proof. Here's the statement of mathematical induction: For every positive integer $n$, let ...
1
vote
2answers
25 views

Proof by induction of the Inequality of Harmonic numbers: $H_{2^n} \ge 1+ \frac n2$

My question is, for the question below, in the inductive step, where does $\dfrac{1}{2^{(k+1)}}$ come from?And where does $2^k$ come from in the third last step?
1
vote
1answer
33 views

How many comparisons does it take to find a number in a grid of numbers arranged in an $N \times N$ square

We have an $N \times N$ squares, filled with integer numbers monotonically increasing in "right" and "down" directions. So from any point, if you move left the number will get bigger, or if you go ...
-1
votes
2answers
66 views

Union-closed families of sets (A problem about induction)

$A$ and $B$ are two sets If $A,B \in F,$ then $A \cup B \in F$. Prove by induction that this property applies to a countable number of sets. If $A_i \in F,i \in \mathbb{N}$, then $ ...
-2
votes
3answers
38 views

Proof by induction. how can I solve?

How can I demonstrate this equality: $$1+2q+3q^2...+nq^{n-1}=\frac{1-(n+1)q^n+nq^{n+1}} {(1-q)^2} $$ My attempt: if $n=1$ $$1=\frac{1-2q+q^2} {(1-q)^2}=1$$ Now i demonstrate this equality: ...
0
votes
5answers
74 views

Mathematical induction [duplicate]

Prove that $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ where $n$ is a nonnegative integer. I have seen many questions on this site that contain the answer to this problem and I already know the solution, ...
5
votes
5answers
90 views

Prove by mathematical induction: $\frac{1}{n}+\frac{1}{n+1}+\dots+\frac{1}{n^2}>1$

Could anybody help me by checking this solution and maybe giving me a cleaner one. Prove by mathematical induction: $$\frac{1}{n}+\frac{1}{n+1}+\dots+\frac{1}{n^2}>1; n\geq2$$. So after I check ...
4
votes
4answers
62 views

Proving $2^n -1 = \sum_{i=0} ^{n-1} 2^i$ for all $n\geq 1$ by induction

I'm practicing proofs by induction, and equalities seem to be the toughest for me. Can somebody please help to prove that for all integers $n \geq 1$: $$ 2^n -1 = \sum \limits _{i=0} ^{n-1} 2^i\;? $$ ...
4
votes
5answers
109 views

Proving $6^n - 1$ is always divisible by $5$ by induction

I'm trying to prove the following, but can't seem to understand it. Can somebody help? Prove $6^n - 1$ is always divisible by $5$ for $n \geq 1$. What I've done: Base Case: $n = 1$: $6^1 - 1 = ...