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
2answers
36 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
49 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
49 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
56 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
57 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
85 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
0answers
28 views

Validity of a proof by induction

By intuition, I would say that if L1 is a subset of L and that L is regular, then L1 is also regular, because L1 has less states than L2 and therefore there must be an automata for L1 too. However, ...
0
votes
1answer
27 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
86 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
41 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
70 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 ...
3
votes
1answer
152 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
54 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
121 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
68 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) + ...
2
votes
2answers
341 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
365 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
51 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
63 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 ...
2
votes
2answers
249 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
316 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
20 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
56 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.
1
vote
1answer
119 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
47 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
109 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
49 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
362 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
81 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
84 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
42 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
53 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
52 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
386 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
166 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
185 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
97 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
71 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
69 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
91 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
92 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
54 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
272 views

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

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
129 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
35 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
53 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$.
0
votes
1answer
24 views

An inequality related to Stirling Number of the second kind

I want to prove $C_{n,r}^2 \leq C_{n-1,r}C_{n+1,r}$ ($n \geq 2,r \geq 1$) where $C_{n,r}=\dfrac{\binom{n+r+1}{n}(n+r)!}{S_2(n+r,r)r!}$ and $S_2(n,k)$ is the Stirling number of the second kind, ...
1
vote
2answers
69 views

What is wrong with the proof given below?

This problem comes from Solow's book, 2nd edition. What is wrong with the proof given below? If $r$ is a real number with $|r| \leq 1$, then for all integers $n \geq 1, 1 + r + r^2 + \ldots + ...
0
votes
1answer
45 views

How Can I find the summation of divisors of $n^p$.

For Example $n=8$ and $p=2$. So $n^p=64$. And the summation of divisors is $1+2+4+8+16+32+64=127$. But the problem arises when $n=10^6$ and $p=10^6$. Remember u can modulus the result by $100$.
1
vote
1answer
60 views

Least Element $\implies n\geq 2$ Has Prime Factorization: An Analysis of Strong Induction

$$\color{blue}{\text{PROBLEM}}$$ Show every natural number $n\geq 2$ has a prime factorization. $$\text{TYPICAL SOLUTION}$$ Base case: $2$ is prime, so it is its own prime factorization. ...