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
0answers
58 views

Matrix Induction proofs using $\rm mod$.

Please could someone advise me on where to even start with this question. Thanks in advance Let $A$ be an $n\times n$ matrix, for some $n\geqslant 1$. Given any prime number $p\gt1$, write $A_p$ for ...
2
votes
0answers
140 views

Homework Question for a 15 year old

My younger brother(age: 14 years 7 months) and his classmates were given a set of eight questions by his class-teacher, which included the following two questions: (i) Find, if you can, the fallacy ...
3
votes
1answer
123 views

Why is this more-detailed proof more acceptable than its trivial counterpart?

Say that we're asked to give a proof of 'proof by induction'. i.e. for some property $P$, proving that $$\forall n,P(1) \wedge [P(k) \implies P(k+1)] \implies \forall n, P(n)$$. Now, I understand ...
0
votes
1answer
96 views

Is this a Correct Proof of the Principle of Complete Induction for Natural Numbers in ZF?

I have reviewed a number of previous posts on this subject without finding an answer to my own point of interest, which is a proof that is closely related to ZF axioms and doesn't pre-suppose results ...
3
votes
1answer
36 views

Number of ways to color such that one color always leads

There are n boxes drawn out in a line. We have two colors, blue and red. We start coloring boxes from left to right. At any instant we want to color the boxes in such a way that number of boxes ...
0
votes
1answer
65 views

Show that $b_n > b_{n-1}$ where $\frac{a_n}{b_n}$ are the n:th harmonic number

Let $H_n=\frac{a_n}{b_n}$ where $H_n$ is a n:th harmonic number and $a_n$ and $b_n$ are coprimes. 1/ If $n$ is a prime power, show that $b_n > b_{n-1}$ 2/ Find the integer factorization of ...
0
votes
2answers
86 views

Integral of $\sin^n(x)$, recurrence relation, some properties

Practicing the manipulation of recurrence relations, I'm stuck on this : Defining $I(n)=\int_{0}^{\pi/2}sin^n(x)dx$, I got the recurrence relation $nI(n)=(n-1)I(n-2)$ for $n\ge2$. Now I'm also ...
0
votes
1answer
22 views

Lemma about a prime ideal in a commutative ring with identity

I am trying to prove the Cyclotomic polynomial is irreducible over $\mathbb{Q}[x]$ for any prime $p$ using Eisenstein's Criterion. However, I would like to be more specific and prove the following ...
2
votes
5answers
110 views

$6^{(n+2)} + 7^{(2n+1)}$ is divisible by $43$ for $n \ge 1$

Use mathematical induction to prove that 6(n+2) + 7(2n+1) is divisible by 43 for n >= 1. So start with n = 1: 6(1+2) + 7(2(1)+1) = 63 + 73 = 559 -> 559/43 = 13. So n=1 is divisible Let P(k): ...
0
votes
9answers
103 views

Proof by induction: Prove that $6$ divides $9^n - 3^n$

Induction: prove that $6| 9^n - 3^n$, where $n$ is a positive integer inductive step: trying to prove $6| 9^{k+1} - 3^{k+1}$, $= 9^k \cdot 9 - 3^k \cdot 3$ $= 6(\frac3 2 \cdot 9^k - \frac1 2 \cdot ...
1
vote
2answers
39 views

Induction: the complement A1 U A2 … U An is the intersection of Ac 1, Ac 2, …, Ac n

Prove by induction that the complement of $ A1 \cup A2...An = A1^c \cap A2^c ...\cap An^c$ My approach: basic step is true, $\overline A1 = A1^c$, then assume $ A1 \cup A2...Ak = A1^c \cap A2^c ...
0
votes
3answers
62 views

Induction: prove $2n^2 < 10\cdot n!$

Prove that $2n^2 < 10\cdot n!$, where $n$ is a positive integer My approach: $P(1)$ is true, and I'm trying to prove that $2(k+1)^2 < 10 (k+1)!$ Assume $2k^2 < 10\cdot k!$, and $2k^2 * ...
1
vote
2answers
37 views

Proof by induction using logarithms

I have come across a question while studing for my exams prove $$\log_2 x < x \text{ when }x>0$$ I know I have to solve it using a base case eg when $x=1$ then assume a inductive step $x=k$ is ...
1
vote
1answer
32 views

Inductive step assumption for all numbers up to $n$

I know that the inductive step should be "for all $n$ (if $P(n)$ then $P(n+1)$)" and NOT "if (for all $n$ $(P(n)$)) then (for all $n$ ($P(n+1)$))" - see this answer. But can it be like "if (for all ...
0
votes
3answers
72 views

Prove that $n = 2a + 3b$.

How can I prove by induction that for any natural number $n$ there exists integers $a,b$ so that $2a+3b=n$ I can prove the base case, and I can imagine why it works but how can I prove it ...
0
votes
2answers
32 views

Using induction to prove an equation

Use induction to show that $n(n + 1) < 2^n$ for all $n \ge 5$. Assuming is true for $n = 5$, $5(6) < 2^5$ is true. How can I prove this using induction?
1
vote
1answer
28 views

Induction proof $2^{n+1}-1$ when n is 50

There are 50 of YES or NO questions. Supposed store them into a binary tree. Each path from root to leaf implies a possible answer to the questions. The number of vertices for $n$ question is ...
0
votes
0answers
18 views

I need to prove by induction $(n-1)!\int_0^1{dx_1\:\ldots\:\int_0^1{dx_n\:\delta(x_1+\ldots+x_n-1)}}=1$ [duplicate]

Prove by induction $$(n-1)!\int_0^1{dx_1\:\ldots\:\int_0^1{dx_n\:\delta(x_1+\ldots+x_n-1)}}=1$$ I can check the cases $n=1,2,3$ but I don't know how the prove the general case. Thank you very much! ...
1
vote
1answer
31 views

Summation Induction when lower limit is not 1

The question is use induction to prove that $$\sum_{r=2}^n (r^2+r+1)r! = (n+1)^2n!-4$$ I don't understand how to even get the P1 statement since when I substitute r = 2 into the LHS and n = 1 into ...
0
votes
2answers
153 views

Prove the commutativity property of addition of natural numbers by induction

the background I'm allowed to deal with to solve this problem is as follows: Definition of +: \begin{equation} m+0=m\quad \text{for all}\quad m \in \mathbb{N} \\ m+(k+1) = (m+k)+1 \end{equation} in ...
2
votes
5answers
111 views

Proof via induction $1\cdot3 + 2\cdot4 + 3\cdot5 + \cdots + n(n+2) = \frac{n(n+1)(2n+7)}{6}$

(b) Prove that for every integer $n \ge 1$, $$1\cdot3 + 2\cdot4 + 3\cdot5 + \cdots + n(n+2) = \frac{n(n+1)(2n+7)}{6}$$ This is the second part of a two part question. Part (a) was the following: ...
1
vote
2answers
53 views

Mix of contour integrals and mathematical induction?

I'm trying to compute $I:= \int_ {0}^{2\pi} \cos ^{2n} \theta d \theta $ Based on the following theorem: $ \Large\int_{0}^{2\pi} F(\cos\theta,\sin\theta)d\theta = \int_{\left|z\right| = 1} ...
0
votes
2answers
57 views

Prove that for every integer $n \ge 1$, $1 + \frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+ … +\frac{1}{\sqrt{n}}\le 2\sqrt{n}$

I understand that this is an induction question. I start with the base case (n=1): $$1 < 2 \tag{That works!}$$ Induction step: Assume the statement works for all $n = k$, Prove for all $n = ...
0
votes
3answers
38 views

induction help proving the sum of the n powers of 2

How do i prove using mathematical induction to prove that the sum of the firstn powers of 2 that can be computed by Evaluating function m(n) = $2^n -1$. $\sum_{k=0}^{n-1}2^k=1+2+4+...+2^{n-1} = ...
2
votes
2answers
42 views

To prove $m$ is not a square of a natural number

Let $m$ be a natural number with digits consisting if only $6$'s and $0$'s p. Prove that $m$ is not the square of a natural number.
1
vote
1answer
27 views

List results of exponentiation, with natural bases and exponents

I am looking for a way to construct an ordered set like $\{2^3, 2^4, 3^3, 2^5, 2^6, 3^4, 5^3, 2^7...\} = \{8, 16, 27, 32, 64, 81, 125, 128...\}$ Preferably, but not necessarily, with all bases ...
3
votes
1answer
79 views

Proving that nth derivate of $x e^{-x}$ is $(-1)^n (e^{-x})(x-n)$ by induction.

I'm quite stuck on this. How would you prove that the $n^{th}$ derivative of $x e^{-x}$ if the $(-1)^n (e^{-x})(x-n)$ by induction? I did: $\frac{d}{dx}(x e^{-x})=(e^{-x}) - x(e^{-x})$ Now I have ...
1
vote
3answers
70 views

Induction proof $F(n)^2 = F(n-1)F(n+1)+(-1)^{n-1}$ for n $\ge$ 2 where n is the Fibonacci sequence

Prove that $F{_n}^2 = F_{n-1}F_{n+1}+(-1)^{n-1}$ for n $\ge$ 2 where n is the Fibonacci sequence F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8 and so on. Initial case n = 2: $$F(2)=1*2+-1=1$$ It is true. ...
0
votes
3answers
51 views

Prove by mathematical induction for every natural number n. $5+25+125+\cdots+5^n=5/4(5^n-1)$

There's one thing I don't understand. In the work shown for this problem in the image below, why is it adding $5^{k+1}$ to both sides? http://imgur.com/d369K5Y (Part 1) http://imgur.com/X9Q6aTi ...
1
vote
3answers
42 views

Induction proof $a_n$ is even for n $\ge$ 1

$$a_1=0, a_2=2, a_3=2, ... a_k = a_{k-2}+3a_{k-3}$$ for k $\ge$ 4 Initial case n = 1 given above it is true as zero is divisible by 2. Let n = k. Assume that $a_{k+1} = a_{k-2+1}+3a_{k-3+1} $ ...
0
votes
0answers
46 views

Help proving by induction that the determinant is equal to: $(-1)^{\frac{n(n-1)}{2}}\cdot a_{1n}\cdot a_{2n-1} \cdots a_{2n1}$

Help proving that the determinant is equal to $(-1)^{\dfrac{n(n-1)}{2}}\cdot a_{1n}\cdot a_{2n-1} \cdots a_{2n1}$ $$ \begin{vmatrix} 0 &0 & \dots &0 &a_{1n}\\ 0 &0 & \dots ...
-2
votes
3answers
95 views

Proof by induction that I'm stumped on. [closed]

$$\sum \limits_{k=1}^{n}k(_k^n)=n2^{n-1} $$ I'm trying to solve this by induction but I have no idea where to start and induction was not taught very well so I'm trying to get it cleared up in any ...
0
votes
1answer
52 views

Use the principle of mathematical induction to show that the given statement is true for all natural numbers n.

Use the principle of mathematical induction to show that the given statement is true for all natural numbers n. $S_n: 11+23+35+...+(12n-1)=n(6n+5)$ My work: $S_1:(12*1-1) \overset?= 1(6*1+5)$ $11 ...
2
votes
2answers
25 views

Solving divide and conquer recurrence

I have a recurrence $T(n)$ with only powers of two being valid as values for $n$. $$T(1) = 1$$ $$T(n) = n^2 + \frac{n}{2} - 1 + T(\frac{n}{2})$$ I tried to substitute $n=2^m$, which yields the ...
1
vote
2answers
88 views

Use the recursive definition of summation together with mathematical induction to prove a sequence

Use the recursive definition of summation together with mathematical induction to prove that for all positive integers $n$ if $a_1, a_2,\ldots, a_n$ are real numbers, then $$\sum_{k=1}^n(3a_k - 2k + ...
1
vote
1answer
20 views

inductive proof of binary existence

Can someone help me witha well exlpained inductive proof of option 2 problem 2. I ha e read many different ones but they dont really make sense to me and I need to know how to do this for my final. ...
-2
votes
1answer
54 views

Prove by indution [closed]

Can someone help me with this homework question. Prove the following by induction $$\sum_{k = 1}^n k {n \choose k} = n \cdot 2^{n - 1}.$$ Thanks
1
vote
0answers
17 views

greatest common divisor via induction? [duplicate]

could someone provide a nice explaination for the following problem. I´m repeating some old exercises and stuck with this one: I have to prove via induction from $(n-1)$ to $n$ for all natural $n,m$ ...
1
vote
2answers
109 views

Find an explicit formula for the recursive sequence (tips?)

Problem: A sequence is defined recursively as follows: Sk = 2k - Sk - 1, for all integers k greater than or equal to 1 S0 = 1 Use iteration to guess the explicit formula for the sequence. Use ...
0
votes
0answers
12 views

Two languages proof by Induction [duplicate]

I have a question that states - Using proof by induction, prove formally that L(R*) = L((R*)*) -- Where R is a regular expression over a non-empty alphabet. I have am struggling to relate it back to ...
0
votes
0answers
25 views

Proof by Induction on two languages [duplicate]

I have a question that states - Using proof by induction, prove formally that L(R*) = L((R*)*) -- Where R is a regular expression over a non-empty alphabet. I have am struggling to relate it back to ...
1
vote
1answer
279 views

induction proof for kleene star

i am going through some past exam paper questions on regular languages for some revision, and i am having a bit of trouble with converting general ideas into formal mathematical proofs. the question ...
2
votes
4answers
99 views

Prove $n^2(n^4-1)$ is divisible by 60 using Mathematical Induction.

Base step: p(2)=4 * 15= 60 Inductive Hypothesis: Assuming p(k) = $k^2(k^4-1)$ = 60q Induction: p(k+1)= $(k+1)^2[(k+1)^4-1]$ = $(k+1)^2[(k+1)^2 + 1][(k+1)^2 - 1]$ = ...
11
votes
3answers
142 views

$1!+2!+\ldots+n!$ cannot be the square of a positive integer

I have to prove that $1!+2!+\ldots+n!$ cannot be the square of a positive integer, $\forall n\geq4$. I've tried to do this with induction, but I don't seem to reach any satisfactory conclusion. Any ...
7
votes
2answers
130 views

Prove That the Second Moment is Minimized with a Circle Packing

Graham and Sloane studied the problem of minimzing the second moment of disks on the plane, i.e. minimize $$ U = \frac{1}{d^2} \sum_{i=1}^{n} || \mathbf{p}_i - \bar{\mathbf{p}} ||^2 $$ s.t. ...
1
vote
3answers
80 views

Use mathematical induction to prove that $(3^n+7^n)-2$ is divisible by 8 for all non-negative integers.

Base step: $3^0 + 7^0 - 2 = 0$ and $8|0$ Suppose that $8|f(n)$, let's say $f(n)= (3^n+7^n)-2= 8k$ Then $f(n+1) = (3^{n+1}+7^{n+1})-2$ $(3*3^{n}+7*7^{n})-2$ This is the part I get stuck. Any help ...
1
vote
0answers
40 views

Taylor's Approximation proof by induction

I'm really stuck on this question Let $f(x)$ be a function on $[a,b]$ which is $(n + 1)$ times differentiable at every point, for some natural number $n$. Let $c$ be a point in $(a,b)$. Using ...
0
votes
1answer
45 views

Prove by Induction that: $1+nx\le (1+x)^n$?

$1+nx\le (1+x)^n$, for all real numbers $x>-1$ and integers $n\ge 2$. Can you please also explain a little of the basic step and the inductions step. Thank you in advance.
1
vote
2answers
30 views

$3^a\mid s(n) \Rightarrow 3^a\mid n$

This is not a homework question, neither a championship problem (as far as I've searched in the net), and it came up noticing a singular pattern, involving the powers of $3$: "Prove or disprove that ...
0
votes
2answers
51 views

Consider all subsets of {1, 2, . . . , n}, prove (n + 1)! − 1

Consider all non-empty subsets of {1, 2, . . . , n} having no consecutive elements. Prove that sum of squares of products of these subsets equals $(n + 1)! − 1$: i.e. if $\mathcal{C}_n$ is the set of ...