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

2
votes
4answers
614 views

Proof that the number of diagonals of a polygon is $\frac{n(n-3)}{2} $

For $n \geq 3$ proof that the number of diagonals of a polygon is $\frac{n(n-3)}{2} $ using induction. I don't know how to start this problem, can you give me a hint?
1
vote
1answer
30 views

Proof $\prod_{i = 1}^n \frac{n + i}{2i-3} = 2^n(1-2n)$ using inducction

i'm trying to solve this, using induction. The base step is easy, there's no difficult there. The problem comes in the inductive step, I got to demonstrate that: $$\prod_{i = 1}^{n+1} \frac{n+ 1 + ...
1
vote
1answer
34 views

Is induction starting at $n=0$ on $F[x_1,\dots,x_n]$ correct?

Suppose you have some polynomial ring $F[x_1,\dots,x_n]$ and you want to prove some fact about it by induction on the number of formal variables $x_i$. Is it ever wrong to start with $n=0$? Since ...
0
votes
2answers
38 views

solve by induction

$$\sum_{r=2}^n{1\over r^2-1}=\frac34-{2n+1\over 2n(n+1)}$$ after I got to $n=k+1$ and tried to get both sides equal I got stuck, prove: $n=k+1$ ; $${1\over k^2 -1} + {1\over (k+1)^2 -1}=\frac34 - ...
2
votes
2answers
59 views

How to prove by induction

How to prove by induction? For $n\ge 1$: $\sum_{j=n}^{2n-1} (1/j) = \sum_{k=1}^{2n-1} ((-1)^{k+1}/k)$ 1) Base case $\sum_{j=1}^{1} (1/j) = 1 = \sum_{k=1}^{1} ((-1)^{k+1}/k)$ 2) Induction [Prove ...
2
votes
3answers
54 views

Use induction to prove $2n + 1 \le 2^n$ for $n=3,4,\ldots$

Use induction to prove $2n + 1 \le 2^n$ for $n=3,4,\ldots$ I've plugged $3$ in for $n$ I get $7 \le 8$ then I set $2(n+1) +1 \le 2^{n+1}$ then I'm lost.
0
votes
2answers
86 views

Proving the geometric sum formula by induction

$$\sum_{k=0}^nq^k = \frac{1-q^{n+1}}{1-q}$$ I want to prove this by induction. Here's what I have. $$\frac{1-q^{n+1}}{1-q} + q^{n+1} = \frac{1-q^{n+1}+q^{n+1}(1-q)}{1-q}$$ I wanted to factor a ...
1
vote
2answers
58 views

Sum from $k=1$ to $n$ of $k^3$

$$\sum_{k=1}^n k^3 = \left(\frac{1}{2}n(n+1) \right)^2$$ I want to prove this using induction. I start with $(\frac{n}{2}(n+1))^2 + (n+1)^3$ and rewrite $(n+1)^3$ as $(n+1)(n+1)^2$, then factor out ...
1
vote
4answers
87 views

Proof for maths induction

prove: $$ \sum_{r=1}^{n}[r^{2}+1](r!)=n[(n+1)!]$$ for all $n \in N$ prove $n=1$, $(1^2+1)(1!)$ = $1[(1+1)!]$ assume true for $n=k$, $(k^2+1)$$(k!)$= $k$$[(k+1)!]$ I got to here : ...
0
votes
1answer
47 views

Regular language restricted to smaller alphabet is regular

Let $L$ be a regular language on some alphabet $\Sigma$, and let $\Sigma_1 \subset \Sigma$ be a smaller alphabet. Consider $L_1$ the subset of $L$ whose elements are made up only of symbols from ...
0
votes
1answer
30 views

Induction with two indexes

I want to prove that if $G$ is a group and $a\in G$, $n,m\in \Bbb Z$, then $a^na^m=a^{n+m}$. I think, that it's easier to prove the case when $n,m\in \Bbb N$. I found this question: Induction (over 2 ...
1
vote
2answers
88 views

proof by maths induction

not sure how to prove this: for all positive intergers prove: \begin{equation} 1+2(2)+3(2^2)+...+n(2^{n-1})=(n-1)(2^n)+1 \end{equation} heres my try: prove $n=1$ : \begin{equation} 1=1 ...
0
votes
1answer
47 views

Proving some sequence of integers by induction

Say I have a sequence like: $0,1,2,0,1,2,0,1,2,\dots$ in other words $1=0$, next $2=1$, third $3=2$ etc. and a formula that I believe works for my sequence. How would I prove that the sequence works ...
0
votes
1answer
83 views

An inequality by induction

I am reading Arthur Engel's Problem Solving Strategies. Section 8. The Induction Principle Problem 24 with its solution are attached . I do not understand the second inequality in the solution on ...
2
votes
3answers
114 views

Help with the algebra in for this number theory proof?

For all $n\geq 1$, prove with mathematical induction $\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$ So far.. I have substituted 1 and saw that the statement is ...
3
votes
1answer
194 views

Solve Recurrence Equation with Induction

Question: Given the recurrence equation for the recursive Fibonacci sequence program: $T(n) = T(n-1) + T(n-2) + b$ $T(0) = T(1) = a$ Using induction, show that $T(n) \leq f(n)$, where $f(n) = c2^n, ...
0
votes
2answers
56 views

Show that $2^n < n!$ for every positive integer $n$ with $n\geq 4$. [duplicate]

Using Mathematical induction prove the above proposition. Basis step can be verified easily. But how can i show that it is true for $p(n+1)$.
0
votes
2answers
214 views

Proving that $fib(n) < (5/3)^n$ for $n \ge 1$ by induction

I know this has been shown before here but no post really answered my question. I had this problem given to me as an induction practice problem and I couldn't solve it without help. When I got the ...
-2
votes
3answers
85 views

Induction proof to find formula

I ran into some problem when I am doing some review. I need to find the formula for the following by exploring the cases n = 1,2,3,4 and prove by induction I have this sequence $$a_n = 1/(1*2) + ...
3
votes
2answers
833 views

Base cases in strong induction

In strong induction, the inductive hypothesis assumes that for all k, P(k) is true. A lot of the proofs I've come across just take this as an assumption. Why then, in some other cases, is it ...
2
votes
6answers
409 views

If $a_1,\ldots,a_n>0$ and $a_1+\cdots+a_n<\frac{1}{2}$, then $(1+a_1)\cdots(1+a_n)<2$.

Assume that $a_1,a_2,\ldots,a_n>0$ and $a_1+a_2+\cdots+a_n<\frac{1}{2}$, and prove that $$(1+a_1)(1+a_2)\cdots(1+a_n)<2$$ I've tried Hölder's inequality (the same result can easily be ...
1
vote
2answers
63 views

How can I come up with a formula for this summation?

I have to come up with a formula for: $$\sum_{0\le i\le n\text{, i is even}}^\ i^2$$ and then prove it by using induction. I know how to do the proof, but I am stuck on coming up with the formula. I ...
0
votes
1answer
74 views

Prove by induction.

I'm working on an assignment and stuck on the same question for the last three hours. I have no idea how I'm suppose to factor and prove this question by induction. Use mathematical induction on ...
3
votes
2answers
376 views

Induction: show that $1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \frac{1}{\sqrt{4}} + … + \frac{1}{\sqrt{n}} < 2\sqrt{n}$

The question: Induction: show that: $$1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \frac{1}{\sqrt{4}} + ... + \frac{1}{\sqrt{n}} < 2\sqrt{n}$$ for $n \geq 1$ My attempt at a solution: First ...
3
votes
2answers
402 views

Fallacious Induction Proof that All Integers are Equal [duplicate]

We're currently learning about induction in my real analysis course. I came up with the following proof that is obviously false but cannot quite figure out why it fails. Here it is... "Any set $S$ of ...
0
votes
1answer
24 views

Conjecture based on limited trail followed by inductive proof

My syllabus says: recognise situations where conjecture based on a limited trail followed by inductive proof is a useful strategy, and carry this out in simple casses e.g. find the nth derivative ...
0
votes
3answers
57 views

How to show $((k+1)!)^2 2^k \leq (2(k+1))!$

How do you show that $((k+1)!)^2 2^{k+1} \leq (2(k+1))!$ This is part of an induction proof and I have not made any progress.
2
votes
1answer
205 views

Integration using induction question

Assume $f : [0, 1] \to \mathbb{R}$ is continuous and arbitrarily often differentiable on $(0, 1)$ (i.e. $f$ is smooth). Denote by $f^{m}$ the $m\text{-th}$ derivative of $f$ with $m∈\mathbb{N}$ and ...
1
vote
0answers
49 views

Proving the base case for a problem in elementary number theory

I have a question about how to prove statements such as the following, using induction: If $p \mid a_1a_2 \cdots a_k$, then $p \mid a_i$ for some $i$, $i = 1, 2, \ldots, k$, where $p$ is prime. ...
3
votes
2answers
127 views

Proving that $xy = yx$ where $x$ and $y$ are both strings.

I am to prove that the following holds for any two strings $x, y \in \lbrace 0, 1\rbrace^*$ $xy = yx$ if and only if $\exists z \in \{0,1\}^*$ and $i,j \in \mathbb N$, such that $x = z^i$ and $y = ...
0
votes
1answer
53 views

Prove the following inequality using induction: $(1 + \epsilon)^n \leq 1+ (2^n - 1)\epsilon$ for every $n \geq 1$ and $0 \leq \epsilon \leq 1$

Prove the following inequality using induction: $$(1 + \epsilon)^n \leq 1+ (2^n - 1)\epsilon$$ for every $n \in \mathbb{N}: n \geq 1$ and $0 \leq \epsilon \leq 1$ I'm familiar with the concept of ...
1
vote
4answers
752 views

Mathematical Induction (summation): $\sum^n_{k=1} k2^k =(n-1)(2^{n+1})+2$

I am stuck on this question from the IB Cambridge HL math text book about Mathematical induction. I am sorry about the bad formatting I am new and have no idea how to write the summation sign. Using ...
1
vote
1answer
116 views

Properties of Natural Numbers and Mathematical Induction

When working with natural numbers how to check that the property we consider is "permissible" to speak about? And not like the property "The smallest positive integer not definable in under eleven ...
2
votes
0answers
85 views

Induction: Show: $\frac{1}{2} \times \frac{3}{4} \times \frac{5}{6} \times … \times \frac{2n-1}{2n} \leq \frac{1}{\sqrt{3n+1}}$ [duplicate]

The question: Show by using induction that: $\frac{1}{2} \times \frac{3}{4} \times \frac{5}{6} \times ... \times \frac{2n-1}{2n} \leq \frac{1}{\sqrt{3n+1}}$ for all $n$ $\in$ $Z_+$ My attempt at a ...
0
votes
1answer
44 views

Difficulties with mathematical induction?

I understand the concept of mathematical induction. Its towards the end where i feel that im missing something. Problem: Prove that $4^n=(4(4^n-16))/3$ for $n\le 3$. I have that the base case is ...
1
vote
1answer
57 views

Am I understanding induction correctly?

Here is an induction proof that I have written for my homework and I want to know if I am understanding this correctly: Prove that for: $ \sum\limits_{i=0}^n i^2 = \frac{n(n+1)(2n+1)}{6}$ My proof: ...
0
votes
2answers
68 views

Bernoulli's inequality by induction

I'm proving Bernoulli's inequality by induction but I noticed something strange. See wikipedia proof: http://en.wikipedia.org/wiki/Bernoulli's_inequality Notice how they multiply both sides of the ...
3
votes
2answers
549 views

Induction: show that $\sum\limits_{k=1}^n \frac{1}{\sqrt{k}} < 2 \sqrt{n}$ for all n $\in Z_+$

The question: show by using induction that $\sum\limits_{k=1}^n \frac{1}{\sqrt{k}} < 2 \sqrt{n}$ for all n $\in Z_+$ My attempt at a solution: The base case $n = 1$ is true. First we use the ...
1
vote
1answer
287 views

Proving by induction that a palindrome contains an even number of $b$s and $c$s

Suppose we want to construct palindromes that contain an $aa$ in the middle if the length is even and an $a$ in the middle if the length is odd. I'm trying to prove by induction that all of these ...
2
votes
1answer
352 views

Prove by induction that $2^{2n} – 1$ is divisible by $3$ whenever n is a positive integer.

I am confused as to how to solve this question. For the Base case $n=1$, $(2^{2(1)} - 1)\,/\, 3 = 1$, base case holds My induction hypothesis is: Assume $2^{2k} -1$ is divisible by $3$ when $k$ is a ...
1
vote
2answers
132 views

How do I go about algebraic manipulation of polynomials with many terms?

I'm doing an inductive proof for a homework problem, and for one step, I need to show that $$ \dfrac{n(n+1)(2n+1)(3n^2+3n-1)}{30} + (n+1)^4 = \\ ...
-1
votes
1answer
83 views

Guess the formula of a matrix

Given a matrix $A$ of size $2\times2$ . $A^2$, $A^3$,$A^4$,and $A^5$ are calculated as seen above. It is required that : Based on your calculation above, Guess a formula for $A^{2n}$ and ...
2
votes
3answers
73 views

Prove $2^n\cdot n! ≤ (n+1)^n$ by induction.

An induction I'm struggling with. Prove $2^n\cdot n! ≤ (n+1)^n$ by induction. An idea was to show that $2^n\cdot n! ≤ 1+n^2$ since $1+n^2 ≤ (n+1)^n$ using Bernoulli. However the inequality is ...
0
votes
3answers
97 views

Induction: show that $\sum\limits_{k=1}^n \frac{k}{2^k} = 2 - \frac{n+2}{2^n}$ for all n $\in Z_+$

So the question in my textbook is: Show by induction that $\sum\limits_{k=1}^n \frac{k}{2^k} = 2 - \frac{n+2}{2^n}$ for all $n$ $\in Z_+$. My attempt at a solution: First of all $Z_+ = 1, 2, 3, 4, ...
0
votes
1answer
162 views

What is mutual induction and how does that differ from regular induction?

http://web.cecs.pdx.edu/~black/CS311/proof_by_mutual_induction.pdf I read this and I fail to see any difference. It's the same thing, prove for n = 0 and then prove for n = k+1.
0
votes
4answers
56 views

I've got a small problem with induction

Let me take a quick example: We want to prove by induction that $3^n-1$ is a multiple of 2, where n is a positive integer. So we start with our "base case" and show that $3^1-1$ is indeed a multiple ...
1
vote
2answers
402 views

Show $\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$ [duplicate]

My question is: show $$\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$$ $$n\geq m\geq 1$$ I tried to do this via induction and failed. there has to be another way of doing this. We could either ...
4
votes
3answers
251 views

Well-ordering principle on $\mathbb N \iff$ Principle of induction $\iff$ Principle of strong induction: How to prove one of them?

Well-ordering principle on $\mathbb N \iff$ Principle of induction $\iff$ Principle of strong induction How to prove one of them ? On Proofwiki there is an article proving the equivalence of the ...
0
votes
2answers
49 views

Stuck in Induction Inequality

I am doing an inequality induction question that looks like this: Prove that $2^n>3n^2$ for $n\geq 8$ So I have done Step $1,2$ but I can't finish step $3$ Step $1$: RTP: $n=8$ LHS=$2^8=256$ ...
2
votes
1answer
60 views

proof by induction to fourier problem

So if $h_n (t) = e^{\pi t^2}\frac{d^n}{dt^n}(e^{-2\pi t^2})$. Show proof by induction that $$\widehat{h_n}=(-i)^n h_n$$ Any ideas how to go about with this one? When $n=0 \to \widehat{h_0}=h_0$.