1
vote
1answer
73 views

Prove $\frac {1} {1+x^2} = \sum^{n-1}_{j=0} (-1)^j x^{2j} + (-1)^n \frac {x^{2n}} {1+x^2}, x\in \mathbb R, n \in \mathbb N$ by induction

Prove $\frac {1} {1+x^2} = \sum^{n-1}_{j=0} (-1)^j x^{2j} + (-1)^n \frac {x^{2n}} {1+x^2}, x\in \mathbb R, n \in \mathbb N$ by induction. $n = 1$: $\sum^{(1)-1}_{j=0} (-1)^j x^{2j} + (-1)^n \frac ...
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 = ...
1
vote
4answers
56 views

prove by induction: $3 + 5 + 7 + … + (2n+1) = n(n+2)$

Use the principle of mathematical induction to prove that $$3 + 5 + 7 + ... + (2n+1) = n(n+2)$$ for all n in $\mathbb N$. I have a problem with induction. If anyone can give me a little insight ...
0
votes
2answers
43 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
66 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 ...
1
vote
2answers
47 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 ...
1
vote
2answers
70 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 = \\ ...
2
votes
4answers
109 views

Stuck while trying to prove $2k^3 \geq (k + 1)^3$…

how can I prove the following: $2k^3 \geq (k + 1)^3$ This is the final part of the elaborate proof for $2^n > n^3 $ give $ n \geq 10$ I have used induction and end up with: $ 2^{K+1} > 2k^3 $ ...
-4
votes
1answer
40 views

Prove by induction that [closed]

Prove by induction that: $(1+\dfrac{1}{n})^n>2$, $\forall n \in \mathbb N, n>1$ $(1+\dfrac{1}{n})^n<3, \forall n \in \mathbb N$ I don't know how to do the inductive step.
2
votes
2answers
146 views

Use induction and Newton's binomial formula to show that $\binom{n}{0}+\binom{n}{1}+\cdot+\binom{n}{n}=2^n, \forall n\in \mathbb N$ [duplicate]

Use induction and Newton's binomial formula to show that: $ i)$ $ \binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n, \forall n\in \mathbb N$ $ ii)$ ...
0
votes
1answer
32 views

Suppose $a_{i}+1=a_{i}q, \forall i \in \mathbb N$, show by induction that if $ q\neq1$, $a_{1}+…+a_{n}=\dfrac{a_{n+1}-a_{1}}{q-1}$

Suppose $a_{i}+1=a_{i}q, \forall i \in \mathbb N$, show by induction that if $ q\neq1$, $a_{1}+...+a_{n}=\dfrac{a_{n+1}-a_{1}}{q-1}, \forall n \in \mathbb N$ Let $P(n)$ be the proposition we want to ...
0
votes
3answers
56 views

Prove by induction that for $q\neq1$, we have $1+q+…+q^{n-1}=\dfrac{q^{n}-1}{q-1}, \forall n\in \mathbb N $

Prove by induction that for $q\neq1$, we have $1+q+...+q^{n-1}=\dfrac{q^{n}-1}{q-1}, \forall n\in \mathbb N $ Let $P(n)$ be the proposition we want to prove. For $P(1)$ we have: ...
0
votes
1answer
68 views

Which natural numbers satisfies $n^2<2^n$ and why? using mathematical induction [duplicate]

Which natural numbers satisfies $n^2<2^n$ and why? using mathematical induction
0
votes
2answers
68 views

How $x^2$ increases by $x+1/x$? [duplicate]

I was going through one of the topic "Introduction to Formal proof". In one example while explaining "Hypothesis" and "conclusion" got confused. The example is as follows: If $x\geq4$, then $2^x ...
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.
1
vote
2answers
41 views

algebra help in AoCP intro to induction

In the introduction of mathematical induction, section 1.2.1 of Knuth's Art of Computer Programming, I'm struggling with (4) especially this relation: $\phi^{n-2} +\phi^{n-1} = \phi^{n-2}(1+\phi)$ ...
0
votes
0answers
40 views

Proof that $ k^2<2^k$ [duplicate]

I'm struggling with this problem of proof by induction: For any natural number $k\geq 5$, prove that $k^2<2^k$. I assumed that $k^2<2^k$ I want to show that $(k+1)^2<2^{k+1}$ The ...
2
votes
6answers
113 views

Proof that $n^3-n$ is a multiple of $3$. [duplicate]

I'm struggling with this problem of proof by induction: For any natural number $n$, prove that $n^3-n$ is a multiple of $3$. I assumed that $k^3-k=3r$ I want to ...
4
votes
2answers
178 views

What is a good example to show high school students why a proof for induction is a reasonable kind of proof?

I teach average-level high school students who have not had much beyond Algebra 1. I want to show them why induction makes sense. I want the sort of problem where it is intuitive that a statement is ...
3
votes
2answers
61 views

Proving by induction that $\sum_{i=2}^n(i^2-i) = \frac{n(n^2-1)}{3}$ for all $n \ge 2$

Doing proof by induction exercises, everything was fine until I tried to do one with $\sum$ : Prove that $$\sum_{i=2}^n(i^2-i) = \frac{n(n^2-1)}{3}$$ holds for all $n \ge 2$. Now, my ...
0
votes
1answer
44 views

help on manipulating this algebraic expression

So I have something like: $\frac {k!}{(k-3)!3!}$ I'm going to add $\frac 12k(k-1)$ to this, and I want to obtain $\frac {(k+1)!}{(k-2)!3!}$ as the result. I'm having trouble with this since I need ...
2
votes
2answers
66 views

Induction: $2^n = \sum_{v=0}^{n} \binom{n}{v}$ [duplicate]

I have to prove the following identity for $n \in \mathbb{N}$: $\displaystyle 2^n = \sum_{v=0}^{n} \binom{n}{v}$ Is there a way to show it through induction? Or is there a easier way? My steps so ...
1
vote
0answers
54 views

How to use an exponent that contains a variable

I am trying to understand a problem that uses mathematical induction to prove the validity of a statement. This is how one section moves to another: $$ 2k + 3 = 2^{k + 1} $$ $$ 2k + 3 = (2k + 1) + 2 ...
3
votes
3answers
96 views

Integers whose sum and product are integers

Let $a$, $b$ be real numbers such that $a + b$ and $ab$ are integers. a. Prove that $a^n + b^n$ is an integer for every natural number $n$. b. Suppose that $a$ does not equal $b$. Prove that ...
-2
votes
2answers
93 views

Mathematical induction or what ??

Simplify $$\left(x+\frac1x\right)\left(x^2+\frac1{x^2}\right)\left(x^4+\frac1{x^4}\right)\ldots\left(x^{2^{n-1}}+\frac1{x^{2^{n-1}}}\right)$$ for $n\in\Bbb N$. how to solve this problem, and am I ...
0
votes
4answers
237 views

Induction: Show that $\sin(2x) + \sin(4x) + \ldots+ \sin(2nx) = \frac{\sin(nx)\sin((n+1)x)}{\sin(x)}$

Show that $\sin(2x) + \sin(4x) + \ldots+ \sin(2nx) = \dfrac{\sin(nx)\sin((n+1)x)}{\sin(x)}$ I tried to use induction. Base case is easy, but I'm stuck at the induction step (from $k$ to $k+1$). ...
2
votes
3answers
150 views

Algebra Textbook

Perhaps this questions was asked already, but I browsed through other threads and couldn't find exactly what I am looking for. I am looking for an Algebra Textbook (high-school/undergrad level) that ...
1
vote
1answer
86 views

The sum of odd powered real numbers equals zero implies the numbers are inverses

Show that if real numbers $a_1,a_2,\ldots,a_n$ satisfy $$a_1^l+a_2^l+\cdots+a_n^l=0$$ for every odd $l$, then for any $a_i$ we can always find some $a_j$ (not necessarily different) such that ...
2
votes
1answer
70 views

if its true for $n$ is it true for $n-1$ (mathematical induction)?

the induction rule , if we suppose that $p(n)$ is true , is $p(n-1)$ true as well? if $1+2+...+n=\frac{n(n+1)}{2}$ is it true than $1+2+...+n-1=n-1(n-1)/2$ (before proving the statement for $p(n+1)$ ...
-1
votes
1answer
87 views

Simple Question about Induction?

let x be a natural number i want to prove that f(x)=$x^2$. suppose that f(x)=$x^2$, f(0)=0 holds we'll prove that f(x)= $(x+1)^2$, in the functional equation we have f(x-y)+f(x+y)=2f(x)+ stuff, ...
3
votes
2answers
126 views

Prove that $2^n>2n$ for all integral values of n greater than 2 [duplicate]

Prove $2^n >2n$ for all integral values of n greater than 2. Let $p_n$ be the statement: $$2^n>2n\ \forall\ n\gt2$$ If the inequality is valid for $n=k$ where $k>2$: $$p_k: 2^k>2k$$ ...
2
votes
4answers
435 views

For what natural numbers is $n^3 < 2^n$? Prove by induction

Problem For what natural numbers is $n^3 < 2^n$? Attempt @ Solution For $n=1$, $1 < 2$ Suppose $n^3 < 2^n$ for some $n = k \ge 1$ It looks like the inequality is true for $n = 0$, $n = 1$ ...
5
votes
2answers
198 views

Suggestions on how to prove the following equality. $a^{m+n}=a^m a^n$

Let $a$ be a nonzero number and $m$ and $n$ be integers. Prove the following equality: $a^{m+n}=a^{m}a^{n}$ I'm not really sure what direction to go in. I'm not sure if I need to show for $n$ ...
1
vote
1answer
62 views

Prove inequality by induction

Once again, I'm stuck in a demonstration by induction, this time, it's really proving that an inequality is valid. So, here is the inequality: Prove that $\binom{2n}{n} \geq (n+5)^2 \ \forall n ...
3
votes
3answers
80 views

A proposed proof by induction of $1+2+\ldots+n=\frac{n(n+1)}{2}$

Prove: $\displaystyle 1+2+\ldots+n=\frac{n(n+1)}{2}$. Proof When $n=1,1=\displaystyle \frac{1(1+1)}{2}$,equality holds. Suppose when $n=k$, we have $1+2+\dots+k=\frac{k(k+1)}{2}$ When $n = k + ...
0
votes
1answer
79 views

Why is this summation formula wrong?

This is the alternate form of the summation formula: $$ \sum^{n}_{k=0} a(c)^k = \frac{ac^{n+1} - a}{c - 1} $$ so why is this wrong? $$ \sum^{n}_{k=0} (-\frac{1}{2})^k = \frac{(-\frac{1}{2})^{n+1} - ...
0
votes
2answers
73 views

Two exercises on mathematical induction

Studying for a test and can't work out how to do two questions on the sample test. (1) Suppose a sequence of numbers $a_1$, $a_2$, $\dots$ is defined recursively by: $$a_1 = 1\qquad\text{and}\qquad ...
0
votes
2answers
119 views

I need help with proofs using mathematical Induction

I need help with this problem: $2+7+12+17+...+(5n-3)=(\frac{n}{2})(5n-1)$
0
votes
1answer
68 views

Prove by induction $ \sum^n_{i=1}(i-1/2) = n^2/2 $

This is a question from a test that I wrote and I'm wondering how do you solve it. Prove by induction that $$ \sum^n_{i=1}(i-1/2) = \frac{n^2}{2} $$ *Provide a Base Case, Inductive Hypothesis, and ...
1
vote
1answer
89 views

prove sum property by induction

Knowing that $(a_i)_{i\ge1}$ prove that $\forall n \in \Bbb N$: $$\sum^n_{i=1}ra_i=r\Big(\sum^n_{i=1}a_i \Big)$$ This kind of demonstrations is totally strange to me, I do not understand how to ...
2
votes
2answers
76 views

Check proof by induction of $\sum_{i=0}^n i^4 = \frac15 n^5+\frac12n^4+\frac13n^3-\frac1{30}n $

$\forall n \in \Bbb N$, I must demonstrate that: $$\sum_{i=0}^n i^4 = \frac15 n^5+\frac12n^4+\frac13n^3-\frac1{30}n $$ $\bullet$ I need to prove that this is true for the first element of the sum (1): ...
1
vote
2answers
231 views

Strong Induction: Prove provided recurrence relation $a_n$ is odd.

I'm not sure if we're allowed to post pictures but I thought it would be easier to read and I didn't see anything in the rules about it. It's question 1. Section 5.4 This question: Here is the ...
1
vote
2answers
133 views

Non-induction proof of $2\sqrt{n+1}-2<\sum_{k=1}^{n}{\frac{1}{\sqrt{k}}}<2\sqrt{n}-1$

Prove that $$2\sqrt{n+1}-2<\sum_{k=1}^{n}{\frac{1}{\sqrt{k}}}<2\sqrt{n}-1.$$ After playing around with the sum, I couldn't get anywhere so I proved inequalities by induction. I'm however ...
2
votes
3answers
376 views

Something kind of like proving the euclidean Algorithm by induction

Let a > b be positive integers. In applying the Euclidean algorithm, we have $a = b q_0$ + $r_0$, $b = r_0 q_1 + r_1$, and $r_{n-1} = r_n q_{n+1} + r_{n+1}$, for all $n > 0$. Prove by induction ...
1
vote
1answer
110 views

Prove $n!>2^n$ for $n\geq4$ using induction. [duplicate]

I just want to know if my proof to this question is correct. First, I proved it was true for $n = 4$. $$4!>2^4$$ $$24>16$$ Then, I assumed that it was true for $n=k$. $$k!>2^k$$ Afterwards, I ...
0
votes
1answer
88 views

Not following algebra in a proof, can anyone please explain it?

So I'm learning mathematical induction as a proof technique (teaching myself discrete math as a foundation for a comp sci class I'm going to be taking). My algebra is a little rusty, and I cannot ...
0
votes
2answers
83 views

Another induction problem (concrete case)

We have the succession and its formula: $$ 1^2+4^2+\cdots+ (3k-2)^2 = \dfrac{k(6k^2-3k-1)}{2} $$ Now we need to apply it for $k+1$: $$ 1^2+4^2+\cdots+ (3n-2)^2 +(3(k+1)-2)^2 = \\ ...
2
votes
2answers
47 views

Why are these two expressions different in this induction problem?

Prove with $n \ge 1$: $$\frac{3}{1\cdot2\cdot2} + \frac{4}{2\cdot3\cdot4}+\cdots+\frac{n+2}{n(n+1)2^n} = 1 - \frac{1}{(n+1)2^n}$$ First, I prove it for $n=1$: $$\left(\frac{1+2}{1(1+1)2^1} = ...
1
vote
2answers
38 views

How does this prove that P(k) of every k is true?

This is an example from my textbook. I'm very rusty with simplifying algebraic expression so i hope you'll forgive me for that. The textbook says there are two rules to Mathematical Induction: 1) We ...