Induction in general is the inference from the particular to the general. Mathematical induction is not true induction, but is a form of deductive reasoning. Its most common use is induction over well ordered sets, such as natural numbers, or ordinals. While induction can be expanded to class ...

learn more… | top users | synonyms

0
votes
4answers
35 views

Proof by induction: $\sum_{k=3}^n k = (n-2)(n+3)/2$ [on hold]

I'm trying to prove the following by induction: $$\sum\limits_{k=3}^n k = \frac{(n-2)(n+3)}{2}$$ Any Ideas about finding the base and induction case?
1
vote
1answer
24 views

Find a closed form

How do I prove (with strong induction) that every positive integer $n$ has a representation in the form $$n = c_r2^r + c_{r−1}2^{r−1} + \cdots + c_2 2^2 + c_1 2 + c_0$$ where $r$ is a nonnegative ...
1
vote
0answers
40 views

Closed form of an equation

How could I find a closed form for the equations 1^3 = 1 , 2^3 = 3 + 5 , 3^3 = 7 + 9 + 11 , 4^3 = 13 + 15 + 17 + 19, 5^3 = 21 + 23 + 25 + 27 + 29 ... and Prove this closed form by induction? Thanks
-6
votes
1answer
40 views

Divisibility in The Integers [on hold]

For $n\ge1$, establish each of the following using induction or congruences: $$8\mid 5^{2n}+7$$ $$15\mid 2^{4n}-1$$$$5\mid 3^{3n+1}+2^{n+1}$$$$21\mid 4^{n+1}+5^{2n-1}$$$$24\mid 2\cdot7^n+3\cdot5^n-5$$ ...
0
votes
5answers
241 views

Proof by induction when numbers are to powers

Prove by mathematical induction: $$ 2^n+3^n < 5^n$$
2
votes
7answers
284 views

problem with simple induction proof

i want to prove that $\forall n\geq 5$ $$2^{n}-1 > n^{2}$$ so the basis is trivial, and in the induction step (n+1), i stuck. i get : $(n+1)^{2} = n^{2} + 2n + 1 < (2^{n} -1)+ 2n+1 = 2^{n} ...
0
votes
0answers
24 views

Induction for k +1 [on hold]

If $\forall n,k \in \mathbb N$ $S_{k+1}(n) = S_k(n) * S_1(n) $ then Prove that $S_{k+1}(n) = (n+1)^{k+1} - 1^{k+1}$. I accept $S_k(n)$ to be true and try to prove for $S_{k+1}(n)$ If that is ...
0
votes
1answer
19 views

Explicit (General) formula for recursive definition.

I am given $a_n=3a_{n-1}+4^n$, $n=1,2,3,....$ and $a_0=1$. First four terms: $$ \begin{align} a_1&=3.1+4^1=3+4=7\\ a_2&=3.7 + 4^2 = 21 + 16 = 37 \\ a_3&=3.37 + 4^3 = 111 + 64 = 175\\ ...
0
votes
3answers
66 views

Proof of $2^n \ge n^2 $ for $n \ge 4 $

I am currently learning induction and I understand the proof except the last line: $$ 2^{n+1} \ge (n+1)^2$$ I'm aware of the fact that, at some point (here $n=4$) an exponential function grows ...
1
vote
3answers
98 views

Find a closed form for the equations $1^3 = 1$, $2^3 = 3 + 5$, $3^3 = 7 + 9 + 11$

This is the assignment I have: Find a closed form for the equations $1^3 = 1$ $2^3 = 3+5$ $3^3 = 7+9+11$ $4^3 = 13+15+17+19$ $5^3 = 21+23+25+27+29$ $...$ Hints. ...
4
votes
1answer
39 views

Show that $n^3 > (n+1)^2$ for $n>2$ using mathematical induction

Is the following a correct way of showing that $n^3 > (n+1)^2$ for $n>2$ using mathematical induction? Thank you in advance! $P(n): n^3>(n+1)^2$ $P(3): 3^3>(3+1)^2$ $27 > 16$ ...
0
votes
2answers
62 views

Using mathematical induction to prove $\frac{1}1+\frac{1}4+\frac{1}9+\cdots+\frac{1}{n^2}<\frac{4n}{2n+1}$

This induction problem is giving me a pretty hard time: $$\frac{1}1+\frac{1}4+\frac{1}9+\cdots+\frac{1}{n^2}<\frac{4n}{2n+1}$$ I am struggling because my math teacher explained us that in ...
2
votes
1answer
25 views

Use induction to prove summation

Use induction on $n\in\Bbb N$ to prove that $$\sum_{k=1}^n\frac{k}{2^k}=2-\frac{n+2}{2^n}\;.$$ I have got as far as to the induction step where I have: $$S(n+1)= 2-\frac{n+3}{2^{n+1}}$$ and this ...
10
votes
2answers
117 views

There are 3 Zero-Sum Numbers!

Prove that for any set of $2n+3$ integers from the interval $[-2n-1,2n+1]$ there is a triple $(x,y,z)$ such that $x+y+z=0$. Example : Choose 5 number from {-3,-2,-1,0,1,2,3} there are x,y,z with ...
1
vote
1answer
33 views

Induction of closed form of summation

On Wikipedia the following closed form is derived - Generalised formula Can someone explain how the closed form below is derived? Edit Solution thanks to graydad
0
votes
1answer
36 views

King Arthur and knights at the round table puzzle

Can you help me with this math problem: Each of the K knights from the round table needs to choose a card which is marked with a number from 1 to N, N >= K. The cards all have different number. ...
0
votes
1answer
48 views

Use mathematical induction to prove that any integer n>=2 is either a prime or a product of primes.

Use strong mathematical induction to prove that any integer $n\ge2$ is either a prime or a product of primes. I know the steps of weak mathematical induction... basis step= $p(n)$ for $n=1$ or any ...
12
votes
5answers
246 views

How to prove $n < \left(1+\frac{1}{\sqrt{n}}\right)^n$

I want to know how to prove the following inequality. For $n = 1, 2, 3, \ldots $ $$ n < \left(1+\frac{1}{\sqrt{n}} \right)^n $$ I tried with math induction but I failed.
0
votes
3answers
38 views

Proof by minimum counter example

I need to prove that $n^4-n^2$ is divisible by 12 by minimum counter example. I understand the process but I don't understand how we arrive at m>=7. I have seen different proofs but I still don't know ...
3
votes
2answers
29 views

Proof by induction for $ \sum_{n}^{M} \cos(2n) = \frac{\sin(M) \cos(M+1)}{\sin(1)} $

Can someone show me an induction for $$ \sum_{n}^{M} \cos(2n) = \frac{\sin(M) \cos(M+1)}{\sin(1)} $$? My problem is doing that induction with $M$, I am not sure how to proceed to get the right side of ...
3
votes
3answers
82 views

prove by induction that $29^n - 21^n$ is always divisible by $8$

I have to prove by induction that that $\forall n \in N,$ $8 | (29^n - 21^n) $ . I understand how to prove things with induction generally, but im not sure where to even start with this one. I ...
0
votes
2answers
42 views

Proof using Induction

Give the induction proof of: $$ 1.2 + 2.3 + k(k+1) = \frac{k(k+1)(k+2)}{3} $$ Is this proof even possible? Not sure how to do.
0
votes
1answer
30 views

Proving Cauchy-Schwarz related proof using induction

So the first thing I was asked to prove was this: If $a_1,a_2,...,a_n$ and $b_a,b_2,...,b_n$ are real numbers, use induction to show. ...
2
votes
0answers
68 views

Prove, using the method of mathematical induction that the following holds true

For natural numbers $n\ge1$ show the following inequality using induction. $$n^{1/n}\le 1+\sqrt{\frac{2}{n}}$$
0
votes
1answer
22 views

Proving number of edges in F = n - k

So if we let F = (V,E) be a forest with n vertices and k connected components (trees), how can I prove that the number of edges in F = n - k ? I was thinking of using induction, but I'm super lost. ...
3
votes
2answers
54 views

Show that it is the solution of the recurrence

I have to show that the solution of the recurrence $$X(1)=1, X(n)=\sum_{i=1}^{n-1}X(i)X(n-i), \text{ for } n>1$$ is $$X(n+1)=\frac{1}{n+1} \binom{2n}{n}$$ I used induction to show that. I have ...
3
votes
4answers
61 views

Prove that $F(1) + F(3) + F(5) + … + F(2n-1) = F(2n)$

(These are Fibonacci numbers; $f(1) = 0$, $f(3) = 1$, $f(5) = 5$, etc.) I'm having trouble proving this with induction, I know how to prove the base case and present the induction hypothesis but I'm ...
1
vote
1answer
18 views

Looking for a way to improve my inductive proof of a statement derived by Rolle's Theorem

The following problem is 'absolutely' clear: Problem: Let $f$ be continuous on the interval $[a,b]$ and $n$-times differentiable on $(a,b)$ and $f$ vanishes on $n+1$ points $x_0< x_1 < \dots ...
1
vote
0answers
20 views

Prove that if there are $2n$ points and $n^2+1$ straight lines connecting them, then there are at least $n$ triangles in this shape.

Proof by induction. For $n=2$, it says that if we have $2(2)=4$ points and $2^2+1=5$ lines connecting them to each other, then there are at least 2 triangles in this shape. Which is true (shown ...
1
vote
1answer
29 views

Inequalities - proof by induction

Proof by induction involving inequalities completely escapes me. I've encountered the following problem: For which non-negative integers n is $n^2 ≤ n!$? Prove your answer (by induction). So, ...
1
vote
3answers
60 views

Using mathematical induction to show that for any $n\ge$ 2 then $\prod_{i=2}^n\left(1-\frac{1}{i^2}\right)=\binom{n+1}{2 \cdot n}$

I'm trying to work through some practice problems but I've been stuck on this for god knows how long now and I've no idea where to even start. Just wondering if it would be possible for someone to ...
1
vote
1answer
60 views

Induction Proof with Combinations?

Show that for all $n\geq0$ $$\binom{n}{0}3^n+\binom{n}{1}3^{n-1}+\dotsc+ \binom{n}{n-1}3^{1}+\binom{n}{n} $$ $$= \binom{n}{0}5^n-\binom{n}{1}5^{n-1}+\binom{n}{2}5^{n-2}-\binom{n}{3}5^{n-3}+\dotsc ...
0
votes
0answers
22 views

different representations of strong induction

I've seen 2 forms of strong induction; just wondering how one follows from the other. $1) f(n_0)\wedge f(n_1)\wedge\cdots \wedge f(n_{k-1})\wedge f(n_k)\wedge \forall_n[f(n-k)\wedge ...
0
votes
3answers
71 views

Prove that $(1+2+3+\cdots + n)^2 = 1^3+2^3+3^3+\cdots + n^3$ for every $n \in \mathbb{N}$ [duplicate]

Prove that $(1+2+3+\cdots + n)^2 = 1^3+2^3+3^3+\cdots + n^3$ for every $n \in \mathbb{N}$. Proof. We will use mathematical induction. If $n = 1$, then we have $(1)^2= 1^3 = 1$. We must show that ...
1
vote
3answers
49 views

Induction Proofs - Mathematics

How do I show by mathematical induction that $2$ divides $n^2 - n$ for all $n$ belonging to the set of Natural Numbers
2
votes
2answers
55 views

How to prove $0 < a_n < 1$ by induction

I know $n \in \mathbb{N}$ and... $$ a_n = \begin{cases} 0 & \text{ if } n = 0 \\ a_{n-1}^{2} + \frac{1}{4} & \text{ if } n > 0 \end{cases} $$ Base Case: $$a_1 = ...
1
vote
1answer
25 views

Showing that a sequence (defined in terms of the previous sequence term) is increasing and bounded above

I'm stuck on this problem and I was wondering if you would be kind enough to help. The question follows: Let $x_{1} = 1$ and $x_{n}$ = $\sqrt{ 1 + 2x_{n-1}}$ for n $\geq$ 2. Show that the sequence ...
1
vote
3answers
27 views

Show that $7\mid 2^{3n} -1 \,\,\,\forall n\in \mathbb N^+$

Show that $7\mid 2^{3n} -1 \,\,\,\forall n\in \mathbb N^+$ Should I prove this by induction? If so, how should I go about it?
5
votes
4answers
60 views

Prove that $ \frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!}+\cdots + \frac{n}{(n+1)!} = 1 - \frac{1}{(n+1)!}$ for $n\in \mathbb N$

I want to prove that if $n \in \mathbb N$ then $$\frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!}+ \cdots+ \frac{n}{(n+1)!} = 1 - \frac{1}{(n+1)!}.$$ I think I am stuck on two fronts. First, I don't know ...
1
vote
1answer
40 views

Induction proof for Fibonacci numbers

I am trying to get a hang on the induction method for proof, but I'm still dubious of many aspect of this proof regarding its application to sequences of integers, such as the Fibonacci sequence. ...
0
votes
2answers
28 views

Prove sum of combinations

Let n and r be positive integers with n ≥ r. Prove that C(r, r) + C(r + 1, r) + ... + C(n, r) = C(n + 1, r + 1) I would like to approach with mathematical induction. However, I don't understand what ...
2
votes
3answers
90 views

How to prove this statement: $\binom{r}{r}+\binom{r+1}{r}+\cdots+\binom{n}{r}=\binom{n+1}{r+1}$

Let $n$ and $r$ be positive integers with $n \ge r$. Prove that Still a beginner here. Need to learn formatting. I am guessing by induction? Not sure what or how to go forward with this. Need help ...
1
vote
3answers
27 views

Proving this $F_{n+1} \cdot F_{n-1} - F^2_n = (-1)^n$ by induction

Where $n \in \mathbb{N}$ and $$ F_n = \begin{cases} 0 & \text{ if } n = 0 \\ 1 & \text{ if } n = 1 \\ F_{n-1} + F_{n-2} & \text{ if } n > 1 ...
0
votes
4answers
42 views

Prove $H_{2^m} \leq 1 + m$, where $H_n = \sum\limits_{k=1}^n \frac{1}{k}$

I really I am not seeing how to continue my approach, which is this. Base case: $m = 1$, so we have $H_2 \leq 2$, where $H_2 = \sum\limits_{k=1}^2 \frac{1}{k} = \frac{1}{1} + \frac{1}{2} = ...
2
votes
4answers
56 views

Equilateral triangle is cut in $4^n$ congruent equilateral smaller triangles

I have an assignment on proof by induction: Suppose n is a positive integer. An equilateral triangle is cut into $4^n$ congruent equilateral triangles, and one corner is removed. (Figure 1 ...
0
votes
1answer
21 views

Strong induction on a sequence, proving two functions are equal?

Excuse the poor title, but my understanding is still a little fuzzy. Admins feel free to change it Here is the question from the book. suppose that $f_{0}, f_{1}, f_{2}...$ is a sequence defined ...
2
votes
1answer
24 views

Induction proof with inequalities

Consider the following claim: $$5^n > 4^n + 3^n + 2^n$$ (a) For what natural numbers is this claim true? (b) Prove that your answer to (a) is correct using induction on n.
0
votes
0answers
22 views

A couple of questions about induction.

I am trying to understand the proof of the theorem 56.4 on page 387. I have asked a related question before and according to user Matt S, we use strong induction here. Where in the body of proving ...
0
votes
1answer
16 views

Lining a rectangular building square panels

I've been working on this for what feels like a lifetime now and I'm just not getting anywhere with it. I'm wondering if someone would be able to explain how to solve it for me? There is a ...
0
votes
3answers
37 views

By induction, show that for ∀n∈N, it is true that: [duplicate]

$$\sum_{i=1}^n 2^i=2+2^2+2^3+.....+ 2^n=2(2^{n}-1)$$ Any help/explanations would be REALLY appreciated. Also in the same vein: By induction, show that $$∀n∈\mathbb N: 11^{n+2} + 12^{2n+1}$$ is ...