3
votes
0answers
27 views

Cauchy-Euler Equation of order $n$

What I wish to prove is that for a Cauchy-Euler equation of order $n$, the substitution $x=e^{t}$ transforms it into a linear differential equation with constant coefficients. To put it as a theorem: ...
0
votes
1answer
17 views

Proving sequence statement using mathematical induction, $d_n = \frac{2}{n!}$

I'm stuck on this homework problem. I must prove the statement using mathematical induction Given: A sequence $d_1, d_2, d_3, ...$ is defined by letting $d_1 = 2$ and for all integers k $\ge$ 2. $$ ...
5
votes
0answers
35 views

My first proof that uses the well-ordering principle (very simple number theory). Please mark/grade.

What do you think about my first proof that uses the well-ordering principle? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof ...
1
vote
4answers
44 views

proof by induction: sum of binomial coefficients

Question: Prove that the sum of the binomial coefficients for the nth power of $(x + y)$ is $2^n$. i.e. the sum of the numbers in the $(n + 1)^{st}$ row of Pascal’s Triangle is $2^n$ i.e. prove ...
2
votes
0answers
38 views

My first proof employing strong induction / complete induction (very simple number theory). Please mark/grade.

What do you think about my first proof employing strong induction? What mark/grade would you give me? Theorem Every natural number greater than 1 is a product of one or more primes. Proof First, ...
17
votes
3answers
664 views

My first induction proof (very simple number theory). Please mark/grade.

What do you think about my first induction proof? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof First, introducing a predicate ...
1
vote
0answers
42 views

Proof by induction for all positive integers

$\sum_{j=1}^n j^2 = \frac{n(n+1)(2n + 1)}{6}$ So I did the obvious and plugged one to show that $1^2 = \frac{1(1+1)(2(1) + 1)}{6}$ Now I am trying to show that $1^2 + 2^2 + ... + n^2 + (n + 1)^2 = ...
2
votes
2answers
77 views

show that $2n\choose n$ is divisible by 2 [duplicate]

I tried using induction, but in the inductive step, I get: If $2n\choose n$ is divisible then I want to see that $2n +2\choose n +1$ $${2n +2\choose n +1} = (2n + 2)!/(n+1)!(n +1)! = {2n\choose n} ...
0
votes
0answers
45 views

The Toad and Frog Game - Proof by Inducation

Toads and Frogs is played on a 1 × n strip of squares. At any time, each square is either empty or occupied by a single toad or frog. Although the game may start at any configuration, it is customary ...
1
vote
3answers
46 views

Simple induction proof

Im having a lot of trouble proving by induction that $3^n + 5^n \geq 2^{n+2}.$ The base step is easy, but I don't seem to find the way to proof the inductive step.
2
votes
2answers
73 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}}$

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 ...
4
votes
3answers
74 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 ...
1
vote
2answers
63 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
2answers
33 views

How to prove statement with two variable by induction

I am trying to prove following statement: $[m,n]$ is a set of functions defined as $f \in [m,n] \leftrightarrow f: \{1,...,m\} \rightarrow \{1,...,n\}$. The size of $[m,n]$ is $n^m$ for $m,n \in ...
1
vote
1answer
77 views

7) Prove that $2n-3 \leq 2^{n-2}$ for all $n \geq 5$ by mathematical induction [duplicate]

Prove that $2n-3\leq 2^{n-2}$ , for all $n \geq 5$ by mathematical induction I have to prove by mathematical induction that: $2n-3\leq 2^{n-2}$ , for all $n \geq 5$
0
votes
2answers
50 views

Prove that $2n-3\leq 2^{n-2}$ , for all $n \geq 5$ by mathematical induction

Prove that $2n-3\leq 2^{n-2}$ , for all $n \geq 5$ by mathematical induction I have to prove by mathematical induction that: $2n-3\leq 2^{n-2}$ , for all $n \geq 5$ Thank you for the Review.
3
votes
2answers
85 views

Is this approach to induction valid?

This is a homework problem: Prove that: $$ 3^{4n+1} + 5^{2n+1}$$ is divisible by $8$ for every natural number $n$. Base case: $$n = 0$$ $$ 3^{0 + 1} + 5^{0 + 1} = 8$$ $$8\bmod8 = 0 $$ Base case ...
1
vote
1answer
77 views

Is this a correct proof by contradiction?

Prove that if a set $A$ of natural numbers contains $n_0$ and contains $k+1$ whenever it contains $k$, then $A$ contains all natural numbers $\geq n_0$. I have attempted a proof by contradiction as ...
1
vote
4answers
207 views

Prove by induction that $10^n -1$ is divisible by 11 for every even natural number

Prove by induction that $10^n -1$ is divisible by 11 for every even natural number n. $0 \notin N$ Base Case: n = 2, since it is the first even natural number. $10^2 -1 = 99$ which is divisible by ...
3
votes
2answers
81 views

Is this how you prove by induction for inequalities?

the question is here: http://cpsc.ualr.edu/srini/DM/chapters/examples/ex2.3.2.html My solution is as below:
0
votes
1answer
46 views

Proof by induction; simplify when adding k+1th term. Understanding induction.

I want to prove: $$(-\frac{1}{2})^0 + (-\frac{1}{2})^1 + \cdots + (-\frac{1}{2})^k + (-\frac{1}{2})^{k+1} = \frac{2^{k+1}+(-1^k)}{3\cdot2^k} + (-\frac{1}{2})^{k+1}$$ How do I simplify the last bit, ...
2
votes
4answers
66 views

Prove that for $n\ge 8$ there are nonnegative integers x and y s.t $3x+5y=n$

Prove that for every integer $n\ge 8$ there are nonnegative integers $x$ and $y$ such that $3x+5y=n$ Attempt: First of all I want to make it clear whether zero is a nonnegative integer. It ...
1
vote
1answer
98 views

Prove by minimum counterexample that $2^n>10n$ for $n>5$

Prove by minimum counterexample that for all integers $n>5$ the statement $2^n>10n$ is true. Attempt: Let $S$ be a set of counterexamples, $S=\{n \in \mathbb{Z_+}: 2^n \le 10n, \space ...
2
votes
1answer
70 views

Use induction on $n$ to prove that $2n+1<2^n$ for all integers $n≥3$.

Use induction on n to prove that $2n+1<2^n$ for all integers $n\geq 3$. My attempt: Let $P(n)$ be the statement $2n+1<2^n$. Base case: Prove that $P(3)$ is true. $LS = 2(3)+1=7$ and ...
3
votes
2answers
91 views

Argument over an induction proof

My friend gave me a problem. Define a sequence $<a_n>$ by the recurrence relation :$$ a_{n+2} - 6a_{n+1} + 8a_n = 0 $$ and $a_1 = 4, a_2 = 8 $. Find the general term $a_n$ in closed form. ...
2
votes
1answer
58 views

Inductive hypothesis vs induction hypothesis

I'm doing a proof by induction. Should I refer to induction hypothesis or to inductive hypothesis in the proof?
1
vote
2answers
47 views

Help with a basic induction proof

The theorem given is: 'If n is a natural number then n can be written in the form 2a + 3b for some integers a and b.' How would I prove this by induction? I've had a go at proving this but I don't ...
1
vote
2answers
134 views

Induction proof with Fibonacci numbers

Prove by induction that for Fibonacci numbers from some index $i > 10$ $1.5^i ≤ f_i ≤ 2^i$ Notice! Because Fibonacci number is a sum of 2 previous Fibonacci numbers, in the induction hypothesis ...
0
votes
1answer
952 views

Mathematical Induction Factorials, sum r(r!) =(n+1)! -1 [duplicate]

How do I prove that $$\sum\limits_{r=1}^{n} r(r!) = (n+1)!-1$$ I was able to get to factor: $LHS = k(k!) + (k+1)(k+1)!$ $\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\, RHS = (k+2)! -1$
1
vote
0answers
55 views

Induction in the caculus of terms - Mathematical Logic

I'm studying logic from the Ebbinghaus's book "Mathematical Logic" and when I tried to solve some of the exercises doubt rises. Given a calculus C consisting of the following rules: ...
3
votes
3answers
52 views

Strong induction doesn't require a base case?

I'm considering the natural numbers to be the nonnegative integers. The principle of strong induction can be stated as follows, "If $P$ is a property such that for any $x$, if $P$ holds for all ...
1
vote
5answers
93 views

Prove that for every $n∈N$ the expression is divisible by $10$?

Prove by induction: $3^{(4n+2)} + 1$ is divisible by $10$. My basic step: $3^{(4n+2)} + 1$, where $n = 1$ gives me $3^6 + 1 = 730$, which is divisible by $10$. However, then I have to do the ...
0
votes
0answers
24 views

Discrete Math Equation Proof (by induction?) [duplicate]

Consider the following description of a game. There are n people playing, one of whom leads the game. They are playing on a playing field with no obstacles. Everyone carries one water balloon. ...
0
votes
1answer
77 views

Strong induction definition clarification

I have a general question about strong induction: Assuming that the base case is 0, if I let my inductive hypothesis be that for all 0 <= k < n some statement is true, and if I prove that that ...
2
votes
1answer
142 views

Question: Prove that a set of connectives is incomplete using structural induction

The proof generally begins with an inductive definition of the set. For example, let's say the set of connectives was {$\oplus$}. Let F be the smallest set such that: 1) Any propositional variable is ...
-1
votes
3answers
101 views

Prove $2^n > 10n^2$ for all sufficiently large integers n.

How do I prove $2^n > 10n^2$ inductively? I know you can prove this to be true using calculus (i.e. taking derivatives). But how would I do it inductively?
0
votes
2answers
351 views

Prove: Dividing an odd number by 2 always produces a remainder of 1

How would I go about proving that for all n belonging to the natural numbers, if any given odd number n is divided by 2, then the remainder is at least 1? I got a hint: Try to reduce the number of ...
2
votes
2answers
63 views

How do I prove that $(1+\frac{1}{2})^{n} \ge 1 + \frac{n}{2}$ for every $n \ge 1$?

How do I prove that $(1+\frac{1}{2})^{n} \ge 1 + \frac{n}{2}$ for every $n \ge 1$ My base case is $n=1$ Inductive step is $n=k$ Assume $n=k+1$ $(\frac{3}{2})^{k} \times \frac{3}{2} \ge (1 + ...
1
vote
1answer
76 views

Prove by induction the following inequality for all n∈N [duplicate]

$\frac1{\sqrt{1}} + \frac1{\sqrt{2}}+\frac1{\sqrt{3}}+...+\frac1{\sqrt{x}}\ge {\sqrt{x}}$ I proved the basic case: and realize it is equal to 1, but I have absolutely no idea how to create prove the ...
0
votes
2answers
84 views

Prove that $1^2 + 3^2 + 5^2+\cdots+(2n-1)^2 = (4n^3-n)/3$ for all $n \in \mathbb{N}$

Prove that $1^2 + 3^2 + 5^2+\cdots+(2n-1)^2 = (4n^3-n)/3$ for all $n \in \mathbb{N}$. How can I solve this with induction? I've been working through a couple examples and for this one I can't relate ...
1
vote
3answers
81 views

Prove a formula in terms of n:

$1+5+9+...+(4n+1)$ I HAVE to use induction, but I am new to induction, so I am a bit confused... I believe I have to use the base case first: so $n=1$ is $4(1)+1=5$, but i get the second term in the ...
1
vote
1answer
67 views

Proof by induction on finite sequence

So I have this problem: Let the finite sequence $a_0,a_1,\ldots,a_n$ be defined by $a_i = b + i\cdot c$. Prove by induction on $n$ that the sum of the terms in the sequence is ...
0
votes
1answer
444 views

proof by induction analysis

Consider the following description of a game. There are $n$ people playing, one of whom leads the game. They are playing on a playing field with no obstacles. Everyone carries one water balloon. ...
0
votes
3answers
177 views

Prove the Number of Additions of Fibonacci Number Algorithm

I am studying for a final exam and I'm having trouble with this question: The following recursive algorithm FIB takes as input an integer $n \ge 0$ and returns the $n$-th Fibonacci number $F_n$: ...
6
votes
5answers
278 views

How can I prove by induction that $9^k - 5^k$ is divisible by 4?

Recently had this on a discrete math test, which sadly I think I failed. But the question asked: Prove that $9^k - 5^k$ is divisible by $4$. Using the only approach I learned in the class, I ...
1
vote
2answers
184 views

Prove $\frac{1}{2} + \cos(x) + \cos(2x) + \dots+ \cos(nx) = \frac{\sin(n+\frac{1}{2})x}{2\sin(\frac{1}{2}x)}$ for $x \neq 0, \pm 2\pi, \pm 4\pi,\dots$

I know that this can be proven inductively. However, I can't get passed the trig. I am pretty sure trig identities can show that the expression above is true for $n=0$, and that if the expression ...
0
votes
3answers
42 views

Prove $4^n > 5*n^2$ where $n\geqslant 3$ is a natural number

I've got this problem out of an exercise booklet and I'm not too familiar with proofs. It looks like I'm supposed to use induction, so far I have: Solving a base case, where $n=3$ So, $4^3 > ...
1
vote
1answer
87 views

Inductive step in the induction: $\sum^{n}_{i=0} q^i = \frac {1-q^{n+1}}{1-q}\times2$

I am trying induction for the following formula: $$\sum^{n}_{i=0} q^i = \frac {1-q^{n+1}}{1-q}\times2$$ I have done the initial step which gives me for $n=1$ for both sites $1+q$ In the inductive ...
1
vote
3answers
353 views

Using induction to prove a result about the Fibonacci sequence

The Fibonacci sequence $F_0, F_1, F_2,...,$ are defined by the rule $$F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2}$$ Use induction to prove that $F_n\geq2^{0.5n}$ for $n\geq 6$ So far I have done the ...
0
votes
0answers
47 views

How to solve this Discrete math problem [duplicate]

This is a question that was on our previous quiz and I didn't know how to answer it, I would like it if I could get some help explaining how to solve such a question. Thank you in advance. Your ...