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
46 views

Prove (by induction) that the given closed form indeed gives the same sequence.

Show that the sequence defined by $𝑏_𝑘=𝑏_{𝑘−1}+2𝑘$ for $𝑘≥2$, where $𝑏_1=4$, is equivalently described by the closed formula $𝑏_𝑛=2𝑛+1$. Start by writing first $6$ terms and then you’ll need ...
1
vote
4answers
101 views

How to prove $1 + 3 + 3^2 + … + 3^{n-1} = (3^n - 1)/2$ by mathematical induction?

$1 + 3 + 3^2 + ... + 3^{n-1} = \dfrac{3^n - 1}2$ I am stuck at $\dfrac{3^k - 1}2 + 3^k$ and I'm not sure if I am right or not.
0
votes
1answer
36 views

prove by induction that $F(n) \leq \left(\frac{1 + \sqrt{5}}{2}\right)^n$

I had the following prove by induction problem in an exam and I didn't do it because I didn't know how to. Could anyone solve it, please? $F(0) = 0$ $F(1) = 1$ $F(n) = F(n-1) - F(n-2)$ $F(n) \leq ...
2
votes
1answer
60 views

$1/4 + 1/ 9 + … 1/n^2< 1$ induction

I have been trying this sum for long and do not know how to proceed. Q. Prove using induction that $$\frac1 4 + \frac1 9 + ... + \frac 1 {n^2} < 1$$ A. By induction. Let $$P(n) = \frac1 4 + ...
2
votes
3answers
57 views

Mathematical Induction question: Prove divisibility by $4$ of $5^n + 9^n + 2$

Use mathematical induction to prove that $5^n + 9^n + 2$ is divisible by $4$, where $n$ is a positive integer.
3
votes
2answers
43 views

Prove inequality using binomial theorem

I have this math question that I'm kind of stuck on. Use the binomial theorem to prove that for all integers $n\ge 2$:$$\left (1+\frac{1}{n}\right )^n < \sum_{j=0}^{n}{\frac{1}{j!}} < ...
1
vote
3answers
35 views

Validity of Inductive Proof - Proof Confirmation

I want to prove this statement using weak induction: Every integer $n>11$ is a sum of two composite integers. When I prove it I get stuck at something basic I believe but unclear for me: I ...
3
votes
4answers
115 views

Prove that $\cos\left(\frac{2\pi}{n}\right)+\cos\left(\frac{4\pi}{n}\right)+\ldots+\cos\left(\frac{2(n-1)\pi}{n}\right)=-1$

May you help on how to start, or where to look for the following question? By using the $n$-th roots of the unity, show that: ...
1
vote
1answer
39 views

Proof by induction: Number of subsets of cardinality 2

We would like to prove by induction that the number of the subsets of cardinality $2$ of a finite set with $n$ elements is given by $\frac{n(n-1)}{2}$. I know the reason why this is true, but how ...
-2
votes
1answer
46 views

Show with mathematical induction using n:

If n men and n women meet in order to marry then there are exactly n! different arrangements such that each man is married with exactly one woman and vice versa. Hint: Give numbers to the men and ...
36
votes
15answers
4k views

Is it a new type of induction? (Infinitesimal induction) Is this even true?

Suppose we want to prove Euler's Formula with induction for all positive real numbers. At first this seems baffling, but an idea struck my mind today. Prove: $$e^{ix}=\cos x+i\sin x \ \ \ ...
1
vote
2answers
40 views

Prove that $\frac{\binom{n}{k}}{n^k} < \frac{\binom{n+1}{k}}{(n+1)^k}$

I have this math question that I'm kind of stuck on. Prove that for all integers $1 < k \le n$, $$\frac{\binom{n}{k}}{n^k} < \frac{\binom{n+1}{k}}{(n+1)^k}$$ I have to use mathematical ...
4
votes
1answer
62 views

How to calculate $\int_0^1\cdots\int_0^1\frac{1}{x_1+x_2+\cdots+x_n+1}dx_1\cdots dx_n$

I met an integral $$\int_0^1\cdots\int_0^1\frac{1}{x_1+x_2+\cdots+x_n+1}dx_1\cdots dx_n$$ I calculated $n=1,2,3$ and made an induction! then i got the result: ...
0
votes
1answer
29 views

Can someone explain the division in this proof of the sum of harmonic sequence? $(n+1)*h(n) - n$

So... this is the explanation my instructor gives in his PDF, but I can't make heads or tails of it. Use mathematical induction to prove that for all positive integers n: H1 + H2 + . . . + Hn = (n ...
7
votes
5answers
661 views

Math induction problem with large numbers

I am trying to figure out how to prove $17^{200} - 1$ is a multiple of $10$. I am talking simple algebra stuff once everything is set in place. I have to use mathematical induction. I figure I need ...
-1
votes
2answers
40 views

Prove using induction or strong induction.

Let the sequence $G_0, G_1, G_2, . . .$ be defined recursively as follows: $G_0 = 0, G_1 = 1$, and $$G_n = (5 G_{n-1}) − (6 G_{n-2})$$ for every n belongs to N, n ≥ 2. Prove using induction or strong ...
0
votes
2answers
64 views

prime numbers and natural numbers

Prove that $n^4+4^n$ is never prime. Here $n$ is any natural number greater than $1$. I have tried by induction hypothesis but to no avail. Can it be done by considering cases when $n$ is odd and when ...
1
vote
1answer
37 views

Can sums be manipulated in this way?

I'm working on an induction proof and I'm trying to manipulate a sum so that I can use my inductive hypothesis. Is the following possible? $$\sum_{i=1}^{3n+4} i = \sum_{i=1}^{3n+1+3}i = ...
0
votes
2answers
39 views

I must do a demonstration by induction of a sum

$\newcommand{\binomial}[2]{\left( \begin{array}{c} #1 \\ #2 \end{array} \right)}$ I have the following sum : $\displaystyle \sum_{k=1}^{n} \binomial{n}{k} = n2^{n-1}$ The $\binomial{n}{k}$ is a ...
0
votes
1answer
9 views

Find LHS for Induction : Total number of triples selected from N items = N(N-1)(N-2)/6

How do I find the LHS for finding the total number of sets of k items each selected from N items. Order does not matter. For e.g. 1+2+3+...+n = n(n+1)/2 How do I find the LHS for my query? RHS is ...
0
votes
1answer
21 views

Proving recursive formula is an integer

This seems like a trivial question, but I can't seem to wrap my head around the proof using induction. Prove: $a_n=2a_{n-1}+a_{n-2}$, with initial condition $a_0=1$ and $a_1=1$, is an integer for $n ...
2
votes
1answer
73 views

$\cos k\theta$ and $\cos(k+1)\theta$ are both rational only when $\theta=\pi/6$

Let $\theta$ be an angle in the interval $(0,\pi/2)$. Given that $\cos \theta$ is irrational and $\cos k\theta$ and $\cos (k+1)\theta$ are both rational for some positive integer $k$, show that ...
3
votes
4answers
199 views

Convincing Myself of Stamp Induction Induction Proof?

Use mathematical induction (and proof by division into cases) to show that any postage of at least 12 cents can be obtained using 3 cent and 7 cent stamps. So for this I understand that it can be ...
0
votes
1answer
48 views

Prove $\log(n) = O(n)$ using induction

I am using the lecture notes here on page 19 (Algorithm Notes 1) example 1 is the inductive proof of $\log(n) = O(n)$. I understand the base case but I don't understand the rest of the example. ...
1
vote
1answer
63 views

Prove $25^n>6^n$ using induction

This seem too simple that I cant even break this down.. Base case: For $n=1$, we have: LHS: $25^1=25$; RHS: $6^1$ So LHS$>$RHS, holds. Inductive, hypothesis: Assume $25^k>6^k$ for some ...
0
votes
2answers
37 views

Does induction find all solutions?

Induction shows that an equality holds for all values of $n$. It doesn't show that this is the only equality or formula for the expression that may hold true, correct? For example, say a question asks ...
1
vote
3answers
86 views

Prove by induction that $3^n +7^n −2$ is divisible by $8$ for all positive integers $n$…

Prove by induction that $3^n +7^n −2$ is divisible by $8$ for all positive integers $n$. So far I have the base case completed, and believe I am close to completing the proof itself. Base ...
0
votes
1answer
27 views

Mathematical Induction Proof, need help on how to explain this one statement.

Use Mathematical Induction to prove that for [; n>=1 ;], that $ b_n=(1/2)((3^n)+1) $ Solution: Basic case: For [; n = 1 ;] $$ b_1 = 2 = 1/2((3^1)+1) $$ Assume that for some k $$ b_k = 1/2(3^k ...
0
votes
1answer
29 views

Discrete Mathematics Proving Question [closed]

I need help with this proof. I am stuck on this question and don't know how to do it: Prove that: $$ \forall n \in \mathbb{N}, \sum\limits_{i=2}^{2^n} \frac{1}{i} \geq \frac{n}{2}$$
1
vote
2answers
51 views

Use mathematical induction to prove the following

So I'm reviewing some problems but I can't seem to understand the part below, doesn't really have to do with induction but just so you guys understand whats going on. Use mathematical induction to ...
0
votes
1answer
33 views

Question on induction regarding monochromatic triangles in graph colourings- Homework related

Let $k$ be a natural number and for each $k$ let $r_k$ be the minimum number $n$ so that if we colour the edges of $K_n$ with $k$ colours then we can find a monochromatic triangle. I have so far ...
1
vote
1answer
25 views

Prove $a\cdot (10)^n\equiv a\cdot 1\pmod 3$ using induction.

Prove $a\cdot (10)^n\equiv a\cdot 1\pmod 3$ using induction. I need to prove this equation to be true not sure how to solve. I know I have to first use one and then plug in $k+1$ but what am I ...
1
vote
0answers
56 views

Prove $3 \cdot 5 \cdot 7 \cdot 11 \cdot prime_n = 2k + 1$ [duplicate]

It is known that any prime greater than 2 is odd. How do I show the combinations of all primes greater than 2 is also odd, $2k+1$? I tried using induction, but what is appropriate for $prime_n$? ...
1
vote
2answers
68 views

Extracting an infinite subsequence

Suppose that $\{a_i\}_{i\in\Bbb N}$ is a sequence of real numbers such that for any $i\in\Bbb N$, there exists $j\in\Bbb N$ with $j>i$ and $a_j>a_i$. How to prove that $\{a_i\}$ contains an ...
0
votes
0answers
42 views

How do I prove using strong form induction a statement regarding winning strategies in this coin game?

Consider a game in which, initially, there is a pile of n coins placed on a table. There are two players who alternate turns. Each player, on her or his turn, removes either one, two, or three coins ...
-1
votes
4answers
81 views

Prove by Mathematical Induction $3^{2n}\equiv 1\pmod 4$ for every natural number n. [closed]

Prove by Mathematical Induction $3^{2n}\equiv 1 \pmod 4$ for every natural number n.
3
votes
2answers
36 views

induction (vs recursion) in proof

This post is about "proof by induction". I want to understand if I've been doing it right. I'm a little confused by something I read in a textbook. My background in math doesn't go beyond ...
0
votes
2answers
33 views

Proving there exists a set such that the sum of the elements equals the product

Show that for all odd positive integer $n$, there exists a set $A$ where $A= [a_1, a_2, a_3, ... , a_n]$ and $\displaystyle\sum_{i=1}^n a_i =\prod_{i=1}^n a_i$. Edit: $a_1,...,a_n$ must be distinct. ...
1
vote
4answers
61 views

Prove inequality by induction $ n^n >(n+1)^{n-1}$

How to prove for $n\ge 2$ the following inequality by induction? I have no idea how to do it. $$ n^n >(n+1)^{n-1}$$ I know that inductive step is $ (n+1)^{n+1} >(n+2)^{n}$, but what next?
-4
votes
1answer
59 views

Proof by Induction $\sum_{i=0}^{k-1} 2^i = 2^k-1$ [duplicate]

Prove mathematical induction $$\sum_{i=0}^{k-1} 2^i = 2^k-1$$
1
vote
2answers
37 views

Is there a principle of Weak Induction for well-founded sets?

I often see the statement that weak and strong induction are equivalent. However, while I understand that this is true for the natural numbers, is this true for any well-founded set of objects? As I ...
1
vote
3answers
51 views

Induction proof for the sum 1+2+4+8+…

I think that the sum 1+2+4+8+16+32+...+n is equal to 2n-1. At least it has worked on all the cases I've tried with, but I can't manage to prove it using induction. I am a newbie when it comes to ...
0
votes
4answers
52 views

Find the general formula for the sequences

1=1 2+3+4+=1+8 5+6+7+8+9=8+27 10+11+12+13+14+15+16=27+64 Find the formula is suggested by these equations?Prove your answer is correct. I saw this question on practice exam and ...
0
votes
1answer
29 views

given $n$ stairs, how many number of ways can you climb either step up one stair or hop up two?

this is the question given $n$ stairs, how many number of ways can you climb either step up one stair or hop up two? I need to include the number of ways for $n=1$ through $6$ as well. My ...
0
votes
1answer
29 views

Proof by induction -inequality

Prove that $ 1 + \frac{1}{2}+ \frac{1}{3} + .... + 1/n < 2\sqrt{n}$ for $n \ge1$ Here's my attempt: Base case: $P(1): \frac{1}{1} \le 2\sqrt{1} = 1 \le 2$ (Base case true) Assume $n = k$ for $k ...
0
votes
3answers
51 views

Proof that $x_{n+1} = 1+\frac{2}{x_n}$ is monotonally decreasing for all $n = 2k$

$x_1 = 1$ $x_{n+1} = 1+ \frac{2}{x_n}$ It's obviously true for $x_2$ and $x_4$, but I'm missing where and how to use the induction hypothesis to prove that $x_{2(k+1)} = x_{2k+2} \leq x_{2k+4} = ...
0
votes
3answers
38 views

How to prove that $\det(Z_{n}) = \det(Z_{n-1}) - \det(Z_{n-2})$?

I'm given an $n \times n$ matrix $Z_{n}$ over $\mathbb{N}$ of which the entry in the $x$-th row and the $y$-th column equals 1 if $|x-y| < 1 $ or $ |x-y| = 1$ and zero otherwise. I'm trying to ...
0
votes
2answers
47 views

Prove that $a_1+\cdots+a_n \geq n$ if $a_1$, $a_2$, … $a_n$ are positive real numbers and their product is $1$

Please give me the proof for the following: Let $a_1,\,a_2,\,\dots\,a_n$ be $n$ positive real numbers whose product is equal to $1$. Prove that $$a_1+\cdots+a_n \geq n$$ and that the equality sign ...
1
vote
2answers
71 views

What is the flaw in this induction proof? [duplicate]

Explain the flaw in the following induction argument which shows all of Lucas’ toys are the same colour. Proof: We will show by induction that: for every integer $n\ge1$, in any group of $n$ of ...
0
votes
2answers
57 views

How is this true? Mathematical induction proof

so I have $1/2 + 1/4 + 1/8 + \ldots + 1/2^n = 1 - 2^{-n}$ to prove by mathematical induction. I did all the steps and I end up with: $$1-2^{-n}+2^{-n-1}=1-2^{-n-1}$$ I tried this out in Wolfram and ...